插入排序、选择排序与冒泡排序

冒泡排序

冒泡排序想必各人并不陌生，其思想是利用双层循环，依次比力每个数，第一次比力前n个数，将最大的数排至最后，再比力前n-1个数，选出次大的数排至倒数第二，以此类推，将无序数组升序排列出来。
直接实现

1. ​
2. void Swap(int* p1, int* p2)
3. {
4.         int* tmp = *p1;
5.         *p1 = *p2;
6.         *p2 = tmp;
7. }
9. // 冒泡排序
10. void BubbleSort(int* a, int n)
11. {
12.         for (int i = 0; i < n; i++)
13.         {
14.         //这里要注意j要小于n-i-1，因为比较的是a[j]与a[j+1]，要防止数组越界
15.                 for (int j = 0; j < n - i - 1; j++)
16.                 {
17.                         if (a[j] > a[j + 1])
18.                         {
19.                                 Swap(&a[j], &a[j + 1]);
20.                         }
21.                 }
22.         }
23. }
25. ​

复制代码

插入排序

插入排序与冒泡排序恰好相反，其是从左到右排至有序，冒泡则是从右至左排至有序。插入排序的思想是利用双层循环依次排挤前 i+1 个数，让前 i+1 个数有序，让第 i+1 个数与前 i 个数比力，让其排为升序或降序，接着将 i++，继续排前 i 个数，直至循环结束。
详细过程如图所示(将每步拆解画出):

代码实现为

1. // 插入排序
2. void InsertSort(int* a, int n)
3. {
4.         //防止数组越界
5.         for (int i = 0; i < n - 1; i++)
6.         {
7.                 int end = i;
8.                 //这里的a[end+1]要注意使用i下标要小于n-1，防止越界
9.                 int tmp = a[end + 1];
10.                 while (end >= 0)
11.                 {
12.                         if (tmp < a[end])
13.                         {
14.                                 //end+1位置的值已经被记录，这里可以直接覆盖
15.                                 a[end + 1] = a[end];
16.                                 end--;
17.                         }
18.                         //如果tmp>=a[end]，就不需要比较，因为前面end个数为有序，a[end]位置为最大的值
19.                         else
20.                         {
21.                                 break;
22.                         }
23.                 }
24.                 //最后把end+1原本位置的值放到合适的位置上
25.                 a[end + 1] = tmp;
26.         }
27. }

复制代码

选择排序

选择排序的思想就是，每次遍历一遍数组，第一次遍历前n个数，找出最大数的坐标，与最后一个位置的数互换，或找出最小数的坐标，与第一个位置的数互换，然后遍历前n-1或后 n-1个数，找出次大或次小的数，进行互换，以此类推。

1. // 选择排序
2. void SelectSort(int* a, int n)
3. {
4.         int end = n - 1;
5.         while (end >= 0)
6.         {
7.                 int maxi = 0;
8.                 //每次取第一个位置的地方作为最大值的坐标进行比较，
9.                 //所以，循环从1开始，不必与自己位置的值比较
10.                 for (int i = 1; i <= end; i++)
11.                 {
12.                         if (a[maxi] < a[i])
13.                         {
14.                                 maxi = i;
15.                         }
16.                 }
17.                 Swap(&a[end], &a[maxi]);
18.                 end--;
19.         }
20. }

复制代码

在此底子上，我们可以进行改进优化，每次取出最大值和最小值的坐标，然后与结尾和开头互换，再begin++、end--，缩小范围将继续找次小和次大的值。
但是优化的选择排序中就要注意一个小细节

按照这个代码，似乎并没有很好的实现排序，但如果细致观察，似乎是这两个位置反了导致的问题，那毕竟为什么会出问题？我们画图来表明。

以是说，细节决定成败，下面是精确的优化后的选择排序代码。

1. ​
2. // 选择排序
3. void SelectSort(int* a, int n)
4. {
5.         int end = n - 1, begin = 0;
6.         while (end >= begin)
7.         {
8.                 int maxi = begin, mini = begin;
9.                 //每次取begin位置的地方作为最大值的坐标进行比较，
10.                 //所以，循环从begin + 1开始，不必与自己位置的值比较
11.                 for (int i = begin + 1; i <= end; i++)
12.                 {
13.                         if (a[maxi] < a[i])
14.                         {
15.                                 maxi = i;
16.                         }
17.                         if (a[mini] > a[i])
18.                         {
19.                                 mini = i;
20.                         }
21.                 }
22.                 Swap(&a[end], &a[maxi]);
23.                 //因为先交换最大值与end位置，要注意最小值在end位置的情况
24.         //此时最小值被换到了记录maxi的位置
25.                 if (mini == end)
26.                 {
27.                         mini = maxi;
28.                 }
29.                 Swap(&a[begin], &a[mini]);
30.                 end--;
31.                 begin++;
32.         }
33. }
35. ​

复制代码

1. // 选择排序
2. void SelectSort(int* a, int n)
3. {
4.         int end = n - 1, begin = 0;
5.         while (end >= begin)
6.         {
7.                 int maxi = begin, mini = begin;
8.                 //每次取begin位置的地方作为最大值的坐标进行比较，
9.                 //所以，循环从begin + 1开始，不必与自己位置的值比较
10.                 for (int i = begin + 1; i <= end; i++)
11.                 {
12.                         if (a[maxi] < a[i])
13.                         {
14.                                 maxi = i;
15.                         }
16.                         if (a[mini] > a[i])
17.                         {
18.                                 mini = i;
19.                         }
20.                 }
21.                 Swap(&a[begin], &a[mini]);
22.                 //因为先交换最小值与begin位置，要注意最大值在begin位置的情况
23.                 //此时的最大值被换到记录mini的位置
24.                 if (maxi == begin)
25.                 {
26.                         maxi = mini;
27.                 }
28.                 Swap(&a[end], &a[maxi]);
29.                 end--;
30.                 begin++;
31.         }
32. }

复制代码

总结加三种排序算法的比力

我们可以通过一些办法来验证
这是利用C语言中的函数，随机天生100000个随机数，分别计算运行这三个排序算法所耗费的时间。

可以清楚的看到，插入排序比其他两个要好很多，插入排序的适应性非常强。
总的来说，插入排序是时间复杂度为O(N^2)的排序算法中最好的一个。希尔排序就是运用了插入排序改良实现的。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。