Java基础学习——各大排序算法一览

2023-08-08 10:00:58

Java基础学习——各大排序算法一览


做了挺久的牛客网了，但好像还么有非常系统地研究过各个排序算法，这怎么能行，这可是稳坐笔试和面试第一把交易的经典问题啊（这时候JVM和spring就不服了，你坐第一把交椅，我们坐啥？行行行，你们三都是大哥，椅子给你们挤一挤，我坐地上抬头仰望你们好吧）。扯多了，还是进入正题吧。

补充几个基本概念：

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序

冒泡排序的思想是：每次比较两个元素，如果他们的顺序错误就把他们交换过来，则可以理解，每一次遍历都可以把最小或最大的元素通过慢慢交换从而“浮”到数组的一端。时间复杂度为O(n2)（从一个公众号“小黑格子屋”的一篇文章里盗来了演示图，包括下面所介绍的其他算法的动态演示图都来源于此），
算法步骤：

  • 比较相邻的两个元素。如果第一个元素比第二个元素大，就交换他们的位置；
  • 重复上面的比较和交换步骤，除了最后一个；

最好情况：当数组已经是正序的时候，速度最快；
最坏情况：当数组是反序的时候，速度最慢。Java基础学习——各大排序算法一览

public class Bubble {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < N - 1; j++)
				if(a[j].compareTo(a[j + 1]) > 0) {
					Comparable temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
		}
	}
}

选择排序

这是一种比较简单的排序算法，遍历一次，把最小的数放在第一个位置；遍历第二次，把第二小的放在第二个位置……无论什么数据进去都是O(n2)的时间复杂度，所以数据规模越小越好，选择排序唯一的好处就是不占用额外的内存了。
算法步骤：

  • 首先遍历一次好到最小的元素，将它放在数组的第一个位置；
  • 再从剩余的数组中找到最小的元素，将它排列在已排数组的末尾；
  • 重复步骤二，直到所有元素均有序。
    Java基础学习——各大排序算法一览 
public class Selection {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int min = i;
			for (int j = i + 1; j < N; j++)
				if (a[j].compareTo(a[min])  < 0)
					min = j;
			Comparable temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

插入排序

插入排序的思想是一次扫描每一个元素，将它们放到合适的位置，这样说似乎有点抽象，那举个例子吧，就想打扑克牌一样，我们在整理自己手牌的时候采用的就是这样的插入排序。插入排序与选择排序不同，插入排序所需的时间取决于输入数组的初始顺序，平均时间复杂度为O(n2)。

算法步骤：

  • 先考虑第一个元素，如果数组中只有一个元素，那自然是有序的；
  • 再考虑第二个元素，将它与第一个元素进行比较，并排好序，这样有序的数组大小就成了2；
  • 依次再考虑后面的每一个元素，并将它们一个一个插入到前面已经排好序的数组中，将原数组遍历完，那就排好序了。

Java基础学习——各大排序算法一览

public class Insertion {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for(int i = 1; i < N; i++) {
			int j = i;
			while(j > 0 && a[j].compareTo(a[j - 1]) < 0) {
				Comparable temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
				j--;
			}
		}
	}
}

希尔排序

上面的三种排序都是基本的初级排序算法，现在我们讲的这种是基于插入排序的快速地排序算法，希尔排序比插入排序更加高效，但希尔排序是一种非稳定的排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序高效的原因是它权衡了子数组的规模和有序性。

希尔排序的基本思想是：先将整个待排序的数组分割成若干个序列分别进行直接插入排序，带整个序列已经基本有序时，再对全体进行一次插入排序。

算法步骤：

  • 希尔排序通过加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们上面说的简单的直接插入排序。

举个例子：
下图显示了增量为4时对包含10个数组元素进行排序的第一个步骤，首先对下标为 0,4,8 的元素进行排序，完成排序之后，算法右移一步，对 1,5,9 号元素进行排序，依次类推，直到所有的元素完成一趟排序，也就是说间隔为4的元素都已经排列有序。
Java基础学习——各大排序算法一览
希尔的原稿中，他建议间隔选为N/2，也就是每一趟都将排序分为两半，因此对于N=100的数组，逐渐减小的间隔序列为：50,25,12，6,3,1。这个方法的好处是不需要在开始排序前为找到初始序列的间隔而计算序列，只需要用2整除N。但是这已经被证明并不是最好的序列。

还有一种很常用的间隔序列：knuth 间隔序列 3h+1。

但是无论是什么间隔序列，最后必须满足一个条件，就是逐渐减小的间隔最后一定要等于1，因此最后一趟排序一定是简单的插入排序。

下面这段代码就是通过knuth间隔序列来实现希尔排序：

public class Shell {
	public static void sort(Comparable[] a) {
		int N = a.length;
		int h = 1;	//h为插入排序的间隔
		while(h < N/3)
			h = 3*h + 1;
		while(h >= 1) {
			for(int i = h; i < N; i++) {
				int j = i;
				while(j >= h && a[j].compareTo(a[j-h]) < 0) {
					Comparable temp = a[j];
					a[j] = a[j-h];
					a[j-h] = temp;
					j = j - h;
				}
			}
			h = h/3;
		}
	}
}

归并排序

归并排序是建立在归并操作上的一种高效的排序算法，归并操作是指将两个有序的数组归并成一个更大得有序数组。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

算法步骤：

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  • 重复步骤 3 直到某一指针达到序列尾；
  • 将另一序列剩下的所有元素直接复制到合并序列尾。

Java基础学习——各大排序算法一览

public class Merge {
	private static Comparable[] aux;
	public static void sort(Comparable[] a) {
		aux = new Comparable[a.length];
		sort(a, 0, a.length - 1);
	}
	
	private static void sort(Comparable[] a, int lo, int hi) {
		if(hi <= lo)
			return;
		int mid = lo + (hi - lo)/2;
		sort(a, lo, mid);
		sort(a, mid+1, hi);
		merge(a, lo, mid, hi);
	}
	
	private static void merge(Comparable[] a, int lo, int mid, int hi) {
		int i = lo, j = mid+1;
		
		for(int k = lo; k <= hi; k++)
			aux[k] = a[k];
		
		for(int k = lo; k <= hi; k++)
			if(i > mid)
				a[k] = aux[j++];
			else if(j > hi)
				a[k] = aux[i++];
			else if(aux[j].compareTo(aux[i]) < 0)
				a[k] = aux[j++];
			else
				a[k] = aux[i++];
	}
}

快速排序

快速排序是一种分而治之的思想在排序算法上的典型应用。从本质上看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法步骤：

  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

如果每次能正好地将数组对半分，这是快速排序的最好算法，，因为这种情况下快速排序的比较次数正好能满足分治递归的公式。
Java基础学习——各大排序算法一览

public class Quick {
	private static void sort(Comparable[] a) {
		sort(a, 0, a.length - 1);
	}

	private static void sort(Comparable[] a, int lo, int hi) {
		if(hi <= lo)
			return;
		int j = partition(a, lo, hi);
		sort(a, lo, j-1);
		sort(a, j+1, hi);
	}

	private static int partition(Comparable[] a, int lo, int hi) {
		int i = lo, j = hi+1;
		Comparable v = a[lo];
		while(true) {
			while(a[++i].compareTo(v) == 1)
				if(i == hi)
					break;
			while(v.compareTo(a[--j]) == 1)
				if(j == lo)
					break;
			if(i >= j)
				break;
			Comparable temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		Comparable temp = a[lo];
		a[lo] = a[j];
		a[j] = temp;
		return j;
	}
}

堆排序

计数排序

桶排序

基数排序

还有几个排序算法没总结，未完待续……

上一篇：在java中,从可比较的意义上扩展了什么


下一篇：小白养成记——Java比较器Comparable和Comparator