排序算法

发表于 | 更新于
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O（N^2） O(N) O(N^2) O(1) 稳定
简单选择排序 O(N^2) O(N^2) O(N^2) O(1) 稳定
直接插入排序 O(N^2) O(N) O(N^2) O(1) 稳定
希尔排序 O(Nlogn)~O(N^2) O(N^1.3) O(N^2) O(1) 不稳定
推排序 O(Nlogn) O(Nlogn) O(Nlogn) O(1) 不稳定
归并排序 O(Nlogn) O(Nlogn) O(Nlogn) O(n) 稳定

1.直接插入排序 （升序）

把待排序的记录按其关键码值的大小逐个插入到一个已经拍好序的有序序列中，直到所有的记录都插入完成为止，得到一个新的有序序列。
当插入第i个元素的时，前面的 i-1个元素都已经排好序了（arr[0],arr[1],arr[2],……arr[i-1],），此时用arr[i]和arr[i-1],arr[i-2]……的排序进行比较，找到第一个小于arr[i]的元素arr[j],将arr[i]插入到arr[j]后面位置，arr[j]和arr[i]之间的元素依次向后移动一个单位。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(int array[], int size){
	for (int i = 1; i < size; i++){
		int k = array[i];
		int j;
		for (int j = i - 1; j >= 0; --j){
			if (array[j] <= k)
				break;
			else 
				array[j + 1] = array[j];
		}
		array[j + 1] = k;
	}
}

总结：

  • 元素集合越接近有序，直接插入排序的时间效率越高
  • 时间复杂度：O(N^2) 最坏O(N^2) 最好的情况 O(N)
  • 空间复杂度：O(1)
  • 稳定性： 稳定 
可优化的地方：在寻找插入位置arr[j+1]时，可使用二分查找的方法快速计算插入位置。

2.希尔排序（缩小增量排序）

直接插入排序的时间复杂度为O(n^2),但是若待排序序列为“正序”时，且数据量比较小，其时间复杂度可提高至O(n),由此可见若待排序列越接近有序，直接插入排序的效率也就越高。

希尔排序是对直接插入排序的优化。希尔排序基本思想就是：先将整个待排序列分割成若干个自序列分别进行直接插入排序，待整个序列接近基本有序时再对整个序列进行一次直接插入排序。

希尔排序的具体流程：
!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20190726140710248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JUX3poYg==,size_16,color_FFFFF
初始化一段数据：9 1 2 5 7 4 8 6 3 5 分别为N0~N9；
第一步先将待排序列分为若干组，{N0,N5},{N1,N5},{N2,N7},{N3,N8},{N4,N9},每一个子序列内部进行直接插入排序，排序结果如图第三行，这个过程被成为一次希尔排序。
然后进行第二次希尔排序将第一次排序得到的序列再此分组，因为已经经历过一次排序，序列“比较有序”所以第二次分组每组多分几个元素，然后每组内进行直接插入排序。
执行若干次希尔排序直至待排序列有序，希尔排序结束。
分组问题和判断待排序列有序问题：
从上述的排序过程可见，希尔排序的一个特点是：子序列的构成不是简单的“逐段分割”而是将相邻某个”增量”的记录组成一个子序列。
如上例子中，第一趟排序时的增量为 5，第二趟排序时的增量为2，第三次排序也就是最后一次排序时增量为1，此时进行的希尔排序就是直接插入排序，但是待排序列已经基本接近有序。
因此当增量为1的时候，是希尔排序的最后一次排序。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void InsertSortGap(int array[], int size, int gap){
	for (int i = gap; i < size; i++){
		int k = array[i];
		int j;
		for ( j = i - gap; j >= 0; j -= gap){
			if (array[j] <= k)
				break;
			else
				array[j + gap] = array[j];
		}
		array[j + gap] = k;
	}
}
void ShellSort(int array[], int size){
	int gap = size;
	while (1){
		gap = gap / 3 + 1;
		//gap 比较大的数 --> 小 --->1 结束
		InsertSortGap(array, size, gap);
		if (gap == 1)
			break;
	}
	Print(array, size);
}

总结：

  • 希尔排序是对直接插入排序的优化。
  • 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  • 时间复杂度：O(N^2)
  • 稳定性： 不稳定

选择排序：每一趟在n-i+1个有数据中选取最大（小）的数据，作为有序数组的第i个元素。

3.直接排序

  • 在元素集合array[i]~array[j]中选择关键码最小的元素

  • 若他不是这组元素中的第一个元素，就将它与这组元素中的第一个元素交换

  • 在剩余的array[i+1]~array[n-1]集合中，重复以上步骤，直到结合只剩下一个元素，排序完成

    代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SelectSort(int array[], int size){
	int min;//记录最小元素的下标
	for (int i = 0; i < size - 1; i++){
		min = i;
		for (int j = i + 1; j < size; j++){
			if (array[j] < array[min]){
				min = j;
			}
		}
		if (i != min){
			int k = array[i];
			array[i] = array[min];
			array[min] = k;
		}
	}
	Print(array, size);
}

总结:

  • 时间复杂度：O(N^2)
  • 稳定性：不稳定

4.堆排序

堆排序是利用堆积树这种数据机构所设计的一种排序算法，它是通过堆来进行选择数据，需要注意的是排升序建大堆，排降序建小堆。
堆的逻辑结构就是一个完全二叉树，存储结构是一个一维数组，数组中的每一个元素满足 

1
2
3
4
5
6
7
//小堆
array[i]<=array[i*2+1];
array[i]<=array[i*2+2];
//或
//大堆
array[i]>=array[i*2+1];
array[i]>=array[i*2+2];

节点node的左节点的数组下标是node2+1,右节点的数组下标是node2+2，根节点的数组下标为0。

处理一个待排序的序列，用堆排序进行排序分为以下几步：
1.建堆升序建大堆，降序建立小堆。

建大堆只能将待排序列中的最大值放在跟节点，小堆反之。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 void GreateHeap(int array[], int size){
	for (int i = (size - 2) / 2; i >= 0; i--){
		AdjustDown(array, size, i);
	}
}
 void AdjustDown(int array[], int size, int root){

	int i = 2 * root + 1;
	int j = 2 * root + 2;

	if (i >= size){
		return;
	}

	int m = i;
	if ( j<size && array[j]>array[i])
		m = j;

	if (array[m] > array[root]){
		Swap(array + m, array + root);
		AdjustDown(array, size, m);
	}
}

2.经过一次建堆操作，找出了最大数，将这个最大的数交换到待排序列的最后位置，然后再对这个待排序列除去交换到最后位置的哪个元素再进行建堆操作，确认新的最值，然后再将新确认的最值和新的序列的最后一位元素继续交换，重复以上操作，直到新的待排序列只剩下一个元素，得到的序列就是升序（降序）的。 

1
2
3
4
5
6
7
8
void HeapSort(int array[], int size){
	GreateHeap(array, size);
	for (int i = 0; i < size; i++){
		Swap(array, array + size - i - 1);
		AdjustDown(array, size-1 - i, 0);
	}
	
}

总结：
时间复杂度:O(N*logN)
空间复杂度:O(1)
稳定性：不稳定

4.快速排序算法：

对于一个待排序列，确认出一个基准值key，将将序列分为小于基准值和大于等于基准值的两个序列，然后再将这两个序列再进行之前的操作分成新的两列，不断往下循环操作使数组分到的数组越来越小，如果分到的新序列里的元素为1或者为0，那么这个序列就是有序的了。
key值可以定为待排序列的第一个元素或者最后一个元素，对待排序列的分组操作有三种实现思想。

4.1按基准值互划分左右区间：

  • huver法

  • 挖坑法

  • 前后指针法

    4.1.1hover法（前后指针法）
    定义两个指针，begin指向待排序列的第一个元素，end指向待排序列的倒数第二个元素，将最后一个元素定位基准值key。
    begin向后移动，当begin所指向的元素小于key时向后移动一个元素，当begin指向的元素大于等于key时begin停止后移，开始移动end，当end指向的元素大于等于key时，end向前移动一位，当end指向元素小于key时停止移动。交换begin和end指向元素，然后继续向后移动begin，大于key停止，向前移动end，小于key停止，begin和end交换所指向元素的值。重复指向这个操作，直至end和begin指向同一个元素。这是将这个元素和基准值进行交换。此时的序列就分为了小于begin指向的基准值的左边序列，和大于等于基准值的右边序列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int hover(int array[], int left, int right){
	int begin = left;
	int end = right - 1;
	int key = array[right];
	while (begin < end){
		while (begin<end&&array[begin] < key)
			begin++;
		while (begin<end&&array[end] >= key)
			end--;
		Swap(array + begin, array + end);
	}
	Swap(array + begin, array + right);
	return begin;
}

4.1.2挖坑法
“挖坑法”听名字就是要从待排序列中取出一个元素，让序列中“空”出一个元素出来。第一步确定基准值key，将待排序列的最后一个元素定为基准值，将这个基准值“挖”出来，定义两个指针分别指向待排序列的第一个元素和倒二个元素分别为begin和end，begin所指向的元素小于key，begin向后移动，当begin指向元素大于key时，将这个元素“挖”出来将之前“挖”出的空填起来，然后移动end指针，当end指向的元素大于等于key时，向前移动一位，否则将end指向的元素“挖”起来，去“填”前面的坑，然后又开始向后移动begin，大于key就“挖”起来填后面的坑，向前移动end指针重复上面的操作，依次移动两个指针，直至两个指针指向同一个位置，而且这个位置是个“坑”，用key“填”这个“坑”，此时待排序列就被分为左边小于key的左序列，和右边大于等于key的右序列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int potholing(int array[], int left, int right){
	int key = array[right];
	int begin = left;
	int end = right;
	while(begin < end){
		while (begin < end&&array[begin] < key)
			begin++;
		array[end] = array[begin];
		while (begin < end&&array[end] >= key)
			end--;
		array[begin] = array[end];
	}
	array[begin] = key;
	return begin;
}

4.1.3前后指针法
老规矩先确定基准值key为待排序列的最后一个元素，定义两个指针begin（初始化为待排序列的第一个位置），prev（初始化为待排序列的第一个位置之前的位置），分别指向右区间最后一个元素（大于等于基准值），左区间最后一个元素（小于基准值），begin，prev为元素的数组下标。两个指针都是先后移动。

先移动begin，当begin指向的元素大于key时begin向后移动，否则prev向后移动一位，交换两个指针指向元素的值，继续向后移动begin，循环以上操作，当begin遍历过待排序列的最后一个元素之后，循环结束，prev指向的元素的值就是key的值。此时待排序列就被分为左边小于key的左序列，和右边大于等于key的右序列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int PartSort(int array[], int left, int right){
	int key = array[right];
	int begin = left;
	int prev = left - 1;
	while (begin <= right){
		if (array[begin] <= key){
			prev++;
			if (prev != begin)
				Swap(array + begin, array + prev);
		}
		begin++;
	}
	return prev;
}

4.2快排实现

按照基准值将待排序列分为左区间后还需继续对两个区间在进行以上三种方法的划分，直至得到的子区间只有一个元素或者没有元素 

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
void _QuickSort(int array[], int left, int right) {
	// 终止条件 size == 0 || size == 1
	// left == right	区间内还剩一个数
	// left > right		区间内没有数
	if (left == right) {
		return;
	}

	if (left > right) {
		return;
	}

	int div; // 比基准值小的放基准值左边，大的放右边后，基准值所在的下标
	div = PartSort(array, left, right);	// 遍历 array[left, right]，把小的放左，大的放右
	//div=hover(array,left,right);
	//div=potholing(array, left, right);
	_QuickSort(array, left, div - 1);	// 分治解决左边的小区间
	_QuickSort(array, div + 1, right);	// 分治解决右边的小区间
}
```  

>总结：
> 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
> 时间复杂度：O(N*logN)
> 稳定性：不稳定  
## 5.归并算法
归并算法的核心思想是分治思想。分治，分之治之。  
对一个无须待排序列，分为有序的子序列，再将这些有序的子序列按合并为一个有序的序列。  
归并排序流程：   
- 申请一段和待排序列大小相同的空间，用来存放合并出来的有序序列
- 申请两个指针，分别指向已经有序的子序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复第三部操作直至有子序列中的值已经全部添加到合并序列中
- 将另一序列中的元素添加到合并序列

void Merge(int arr[], int ind[], int str, int mid, int end){
int new_str = mid + 1;
int i = str;
while (str != mid + 1 && new_str != end + 1){
if (arr[str] <= arr[new_str])
ind[i] = arr[str++];
else
ind[i] = arr[new_str++];
i++;
}
while (str != mid + 1)
ind[i++] = arr[str++];
while (new_str != end + 1)
ind[i++] = arr[new_str++];
for (int j = str; j <= end; j++)
arr[j] = ind[j];
}

void MergeSort(int arr[], int ind[], int str, int end){
if (str < end){
int mid = (str + end) / 2;
MergeSort(arr, ind, str, mid);
MergeSort(arr, ind, mid + 1, end);
//arr已经分为了两个有序的子序列
Merge(arr, ind, str, mid, end);
}
}


>总结：
>时间复杂度：O(N*logN)
>稳定型：稳定