0%

常见排序的总结

插入排序

基本思想

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

直接插入排序

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);
}
  • 本文作者: Tim
  • 本文链接: https://zouchanglin.cn/2732113479.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!