常见排序的总结

插入排序

基本思想

每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的合适位置上去,直到元素全部插完为止

直接插入排序

mark

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入排序 
void InsertSort(int *arr, int n)
{
int index = 0;
assert (arr);
for(index = 1; index < n; index++)
{
// 将当前数据往前插入
int end = index-1;
int temp = arr [index];
while(end >= 0 && temp < arr [end])
{
arr [end+1] = arr [end];
--end;
}
arr [end+1] = temp;
}
}

下图只是演示到将 16 排序到前面的过程
mark

直接插入排序的优化

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
// 插入排序 
void InsertSort_OP(int *arr, int n)
{
int index = 0;
for (index = 1; index < n; index++)
{
int temp = arr [index];
// 通过二分查找 找出待插入元素的位置
int left = 0;
int right = index - 1;

while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (temp >= arr [mid])
left = mid + 1;
else
right = mid - 1;
}

// 将当前数据往前插入
int end = index - 1;
// 搬移元素
while (end >= left)
{
arr [end + 1] = arr [end];
--end;
}
arr [left] = temp;
}
}

由于之前的序列都是有序的,这样的话就不用一个一个进行比较,只要先用二分查找找到插入的位置,这样的话本来需要搬运元素只需要搬运一次就行,很多元素不需要比较一次就搬运一次,这样会提高效率!

总结

元素集合越接近有序,直接插入排序算法的时间效率越高!
最优情况下:时间效率为 $O (n)$
最差情况下:时间复杂度为 $O (n^2)$
空间复杂度:$O (1)$,它是一种稳定的排序算法

希尔排序

又称缩小增量排序,是对直接插入排序的优化
mark
很容易看出,经过这样的分组之后,许多比较大的数字都放在了后面,小数字都放在了前面,只要 gap 不断减小,分组不断变小,最后直到 gap 减到 1 的时候就和直接插入排序没什么区别了!
mark

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ShellSort(int* arr,int len)
{
int gap = len;
assert (arr);
while(gap>1)
{
gap = gap/3+1;
int cur = 0;
for(cur = gap;cur<len;++cur)
{
int end = cur-gap;
int tmp = arr [cur];
while(end>=0 && tmp<arr [end])
{
arr [end+gap] = arr [end];
end -= gap;
}
arr [end+gap] = tmp;
}
}
}

总结

希尔排序是一种 不稳定 的排序,时间复杂度:$N^{1.25} 到 1.6N^{1.25}$

选择排序

基本思想

假设要排升序,每一趟选择一个最大的数字与最后的元素交换,这里所说的最后一个元素是会逐步向前调整的!
mark

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 选择排序 
void SelectSort(int *arr, int n)
{
int index = 0;
assert (arr);
for (index = 0; index < n; index++)
{
int maxPos = 0;
int i = 1;
// 找最大元素的位置
for (i = 1; i < n-index; i++)
{
if (arr [i] > arr [maxPos])
maxPos = i;
}
if (maxPos != (n - index - 1))
Swap (&arr [maxPos], &arr [n-index-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
25
26
27
28
29
30
31
32
33
// 选择排序的优化 
void SelectSort_OP(int *arr, int n)
{
int begin = 0;
int end = n-1;

assert (arr);
while(begin < end)
{
int minindex = begin;
int maxindex = begin;
// 分别找到最大和最小的下标
int i = 0;
for(i = begin;i <= end; ++i)
{
if(arr [i]>arr [maxindex])
{
maxindex = i;
}
if(arr [i]<arr [minindex])
{
minindex = i;
}
}
// 把最小的放在前面,最大的放在后面
Swap (&arr [begin], &arr [minindex]);
if(begin == maxindex)// 修正
maxindex = minindex;
Swap (&arr [end], &arr [maxindex]);
++begin;
--end;
}
}

只不过这种优化的方式需要注意一点(见下图),如果最小的元素恰好是最大的元素需要插入的位置,此时就需要将 minPos 设置为原来 max 的位置,因为最小值已经和 maxPos 位置的值交换了!
mark

总结

时间复杂度:$n^2$
空间复杂度:$O (1)$
这是一种不稳定的排序

堆排序

堆排序有两个关键点

  • 根据数组去建堆
  • 交换首尾元素向下调整

mark

代码实现

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
void HeapAdjust(int *arr,int root,int len)
{
//child 是左孩子的下标
int child = root*2+1;
assert (arr);
while(child<len)
{
// 比较左孩子和右孩子,child 指向大的孩子
if(child+1<len && arr [child+1]>arr [child])
{
child++;
}
// 1. 若大的孩子节点大于根节点,则不再需要调整,跳出循环
// 2. 否则,交换孩子节点和根节点,将根节点继续往下调整
if (arr [child] > arr [root])
{
Swap (&arr [child], &arr [root]);
root = child;
child = child * 2 + 1;
}
else
return;
}
}
// 堆排序
void HeapSort(int *arr, int len)
{
int i = (len - 2)>>1;
assert (arr);
// 建堆
for( ; i>=0; i--)
HeapAdjust (arr, i, len);
// 排序
for(i = len-1;i > 0; i--)
{
Swap (&arr [i], &arr [0]);
HeapAdjust (arr, 0, i);
}
}

总结

堆排序的时间复杂度:$N/2 *{log N}$ 其实就是 $logN$
空间复杂度:$O (1)$
稳定性:不稳定

交换排序

冒泡排序

冒泡排序的思想非常简单,如下图,两两比较,每趟排序总可以把最大的放在最后面或者最小的值放在最后面,只需要进行(假设元素个数为 n)n-1 趟冒泡,便可以排序完成!

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 冒泡排序及其优化 
void BubbleSort(int* arr, int len)
{
int index = 0;
int end = 0;
assert (arr);
for(end = len-1;end>0;end--)
{
int flag = 0;
for(index=0;index<end;index++)
{
if(arr [index]>arr [index+1])
{
Swap (&arr [index], &arr [index+1]);
flag = 1;
}
}
if(flag == 0)
break;
}
}

总结

冒泡排序最好情况时间复杂度 $O (n)$,冒泡排序最坏情况下时间复杂度 $O (1)$
冒泡排序空间复杂度 $O (1)$
冒泡排序是一种稳定的排序算法

快速排序

基本思想

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
mark
这样的话左边都是比基准值小的,在右边的都是比基准值大的,根据分治的思想,可以再把左边的序列选出一个基准值,在右边的序列也选择一个基准值,左边的排好了,右边的排好了,整个序列也就排好了!

代码实现_hoare 版本

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
// 快速排序 
int PartSort(int *a, int left, int right)
{
int key = a [right];
int begin = left;
int end = right - 1;
while (begin < end)
{
// 找比基准值大的
while ((begin < end) && (a [begin] <= key))
begin++;
// 找比基准值小的
while ((begin < end) && (a [end] >= key))
end--;
if (begin<end)
Swap (&a [begin], &a [end]);
}
// 最后别忘记把基准值和相遇点交换
if (begin != right - 1)
Swap (&a [begin], &a [right-1]);
return begin;
}
void QuickSort(int *a, int left, int right)
{
assert (a);
if (left >= right)
return;
int div = PartSort (a, left, right);
QuickSort (a, left, div);
QuickSort (a, div + 1, right);
}

前后指针法


这个方式其实不难理解,就是每次将 key 值移动到中间,在 key 左边的值都是比 key 小的值,key 右边的值都是比 key 大的值,这样做分组的的话通过递归就可以完成排序!

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
int PartSort3(int *array, int left, int right)
{
int key = array[right - 1];
int cur = left;
int pre = cur - 1;
while (cur < right)// 说明区间的元素还没有遍历完成
{
if ((array[cur] < key) && (++pre != cur))
Swap (&array[cur], &array[pre]);
++cur;

}
if (++pre != right)
Swap (&array[pre], &array[right-1]);
return pre;
}
void QuickSort3(int *a, int left, int right)
{
assert (a);
if (left >= right)
return;
int div = PartSort3 (a, left, right);
QuickSort (a, left, div - 1);
QuickSort (a, div + 1, right);
}