常见排序算法

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 3,429 | 阅读时长： 15

本篇的排序算法有，冒泡排序，插入排序，选择排序，快速排序，希尔排序，归并排序。

堆排序，计数排序，桶排序，基数排序：常见排序算法2

有关排序的算法例题：排序算法案例

冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示:

冒泡排序

图：冒泡排序过程示意图

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Bubble_Sort {

	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		Bubble_Sort(a);
		for(int i=0; i<a.length; i++)
			System.out.println(a[i]);
	}

	//冒泡排序
    private static void Bubble_Sort(int[] a) {
    	int i, j, temp;
    	for(i = 0; i < a.length-1; i++)
    		for(j = 0; j < a.length-i-1; j++) {
    			if(a[j] > a[j+1]) {
    				temp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = temp;
    			}
    		}
	}
}

算法分析：

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述：

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

动图演示：

插入排序

图：插入排序过程示意图

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Insertion_sort {

	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		Insertion_sort(a);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i] + " ");
	

	}
	
	//插入排序
	private static void Insertion_sort(int[] a) {
		for(int i=0; i<a.length-1; i++) {
			for(int j=i+1; j>0; j--) {
				if(a[j-1] <= a[j])
					break;
				int temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
			}
		}
		
	}
}

算法分析：

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)。

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多{\displaystyle n-1}次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法描述：

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  1. 初始状态：无序区为R[1..n]，有序区为空；
  2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  3. n-1趟结束，数组有序化了。

动图演示：

选择排序

图：选择排序过程示意图

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Select_Sort {
	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		select_Sort(a);select_Sort(a);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();
		
	}

	//选择排序s
	private static void select_Sort(int[] a) {
		for(int i = 0; i < a.length-1; i++) {
			int min = i; //未排序序列中最小数据数组下标
			//在未排序元素中继续寻找最小元素，并保存其下标
			for(int j = i+1; j < a.length; j++)  
				if(a[min] > a[j]) 
					min = j;
			//将最小元素放到已排序序列的末尾
			int temp = a[min];
			a[min] = a[i];
			a[i] = temp;
		}
	}
}

算法分析：

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)。

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述：

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

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

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

动图演示：

快速排序

图：快速排序过程示意图

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Quick_Sort {

	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		quick_Sort(a, 0, a.length-1);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();
	}

	public static void quick_Sort(int[] a, int low, int high) {
		if(low < high) {
			int i = low, j = high, pivot = a[(low+high)/2];
			while(i <= j) {
				while (a[i] < pivot)
					i++;	
				while (a[j] > pivot) 
					j--;
				if(i < j) {
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
					i++;
					j--;
				}else if(i == j)
					i++;	
			}
			quick_Sort(a, low, j);
			quick_Sort(a, i, high);
		}
	}	
}

算法分析：

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)　

快速排序优化及分区扫描法：

希尔排序

希尔排序(Shell’s Sort)，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

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

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

算法描述：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示：

希尔排序

图：希尔排序过程示意图,以23, 10, 4, 1的步长序列进行希尔排序

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Shell_sort {

	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		shell_Sort(a);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();
	}

	public static void shell_Sort(int[] a) {
		int gap = 1,j, len = a.length;
		while(gap < len/3)
			gap = gap * 3 + 1;//动态定义间隔序列。1, 4, 13...
		for(; gap>0; gap /= 3) {
			for(int i = gap; i < len; i++) {
				int temp = a[i];
				for(j = i-gap; j>=0 && a[j]>temp; j-=gap) 
					a[j+gap] = a[j];
				a[j+gap] = temp;
			}
		}
	}
}

算法分析：

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog n)。

归并排序

归并排序（merge-sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法描述：

递归法：

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

动图演示：

归并排序1

归并排序

图：归并排序过程示意图

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Merge_sort {

	public static void main(String[] args) {
		int a[] = {10, 3,19, 32, 4, 23, 323, 34, 2, 35};
		merge_Sort(a);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();
	}

	public static void merge_Sort(int[] a) {
		int len = a.length;
		int [] result = new int[len];
		merge_sort_recusiver(a, result, 0, len-1);
	}

	public static void merge_sort_recusiver(int[] a, int[] result, int start, int end) {
		if(start >= end)
			return;
		int len = end - start, mid = (len/2) + start;
		int start1 = start, end1 = mid;
		int start2 = mid + 1, end2 = end;
		merge_sort_recusiver(a, result, start1, end1);
		merge_sort_recusiver(a, result, start2, end2);
		int k = start;
		while(start1 <= end1 && start2 <= end2)
			result[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
		while(start1 <= end1)
			result[k++] = a[start1++];
		while(start2 <= end2)
			result[k++] = a[start2 ++];
		for(k = start; k <= end; k++)
			a[k] = result[k];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 思路：将数组分为左右两个子数组，递归调用归并进行排序<br />
 *      分别排序完成后，使用辅助的合并函数将两个有序的子数组合并成一个整体有序的数组<br />
 * 时间复杂度：均：O(nlgn)，好：O(nlgn)，坏：O(nlgn)<br />
 * 空间复杂度：需要开辟辅助空间，该辅助空间可以重用，大小为N<br />
 * 非原址排序<br />
 * 稳定性：所有排序都是归并，在左的永远在左，在右的永远在右，稳定<br />
 */
public class MegerSort {
	private static int[] helper;//辅助空间，和arr的长度一样

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		helper = new int[arr.length];
		util.ArrayUtil.printArr(arr);
		megerSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);
	}

	
	public static void megerSort(int[] arr, int p, int r) {
		if(p < r) {
			int mid = p + ((r - p) >> 1);
			megerSort(arr, p, mid);
			megerSort(arr, mid + 1, r);
			meger(arr, p, mid, r);
		}
		
	}
		private static void meger(int[] arr, int p, int mid, int r) {
		System.arraycopy(arr, p, helper, p, r - p + 1);
		int left = p; // 左侧队伍的头部指针，指向待比较的元素
		int right = mid + 1; //右侧队伍的头部指针，指向待比较的元素
		int current = p; //原数组的指针，指向待填入数据的位置
		while(left <= mid && right <= r) {
			if(helper[left] <= helper[right]) {
				arr[current++] = helper[left++];
			}else {
				arr[current++] = helper[right++];
			}
		}
		//如果左侧队伍没比较完，需要将左侧的数依次添加到原队列后面
		while(left <= mid) {
			arr[current++] = helper[left++];
		}
	}
}

算法分析：

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)。

坚持原创技术分享，您的支持将鼓励我继续创作！