详解八大排序（一）------（插入排序，选择排序，冒泡排序，希尔排序） ...

前言

   在日常生活中，我们常常要将各种各样的数据进行排序，例如我要将班上的门生按照数学成绩从大到小的排序，像这种一般环境，编译器自带的sort函数就能满足我们的要求。但是，假如我要将班上姓刘的门生按照数学成绩从大到小的排序呢？
    这种时候，编译器自带的sort函数无法满足需求，我们就需要自己定义一个排序函数。 下面我就要介绍如今的八大排序的原理，代码，以及时间，空间复杂度。
  1.插入排序（InsertSort）

1.1 核心思绪

   直接插入排序的核心思绪是先分组，再比较。
  

   例如上面的数组，有六个数。那么我们就可以先把[3,6]分成一组进行比较，得到[3,6]数组。 再把[3,6,7]分成一组进行比较，得到[3,6,7]数组。再把[3,6,7,1]分成一组，得到[1,3,6, 7]数组。 以此类推，得到[1,2,3,4,6,7]数组。
  1.2 实现代码

1. // 插入排序
2. //插入排序的核心思路就是把i个数分成一组，让第i个数与第i+1个数进行比较
3. //把较大的数放在后面
4. void InsertSort(int* arr, int n)
5. {
6.         for (int i = 0; i < n - 1; i++)
7.         {
8.                 int end = i;//把i个数分成一组
9.                 int tmp = arr[end + 1];//记录最后一个数
11.                 while (end >= 0){
12.                 //把i + 2个数分成一组，当 end >= 0 时
13.                 //说明这一组的数没有全部比较，循环比较大小
14.                         if (arr[end] > tmp){//位于end的数大于最后一个数
15.                                 arr[end + 1] = arr[end];//把位于end的数赋值给end + 1的位置
16.                                 end--;//end--，比较下一个数
17.                         }
18.                         else {
19.                                 break;
20.                         }
21.                 }
22.                 arr[end + 1] = tmp;//退出while循环有两种情况
23.                 //1.end减少到-1，说明这一组的数均大于最后一个数
24.                 //这样end+1 == 0,把最后一个数赋值给0的位置
25.                 //2.break提前跳出循环，说明此时end的数小于最后一个数
26.                 //那么把最后一个数放在end + 1的位置
27.         }
28. }

复制代码

2.选择排序（SelectSort）

2.1 核心思绪

   选择排序的核心思绪是先找到当前数组中的最大和最小数，再放到相应的位置。
  

   例如上面的数组，选择排序中我们会定义好第一个位置（0）和末了一个位置（size - 1），再从数组中找到最小（1）和最大数（7），再把1和7放到相应的位置上。 再定义好第二个位置（1）和倒数第二个位置（size - 2），再从数组中找到第二小（2）和 第二大的数（6），再把2和6放到相应的位置上。 以此类推，直到所有的数排序完。
  2.2 实现代码

1. // 选择排序
2. void SelectSort(int* arr, int n)
3. {
4.         int begin = 0;
5.         int end = n - 1;
6.         //定义最小数据和最大数据的位置
7.         while (begin < end)//当begin小于end时，说明数组中的数据没有比较完，循环比较
8.         {
9.                 int mini = begin, maxi = begin;//先定义一个最小数和最大数
10.                 for (int i = begin + 1; i <= end; i++)//找大找小，从第二个数开始比较
11.                 {
12.                         if (arr[i] > arr[maxi])
13.                         //当前数组轮到的数大于当前的最大数，那么这个数就是新的最大数
14.                         {
15.                                 maxi = i;
16.                         }
17.                         if (arr[i] < arr[mini])
18.                         //当前数组轮到的数小于当前的最小数，那么这个数就是新的最小数
19.                         {
20.                                 mini = i;
21.                         }
22.                 }
24.                 if (maxi == begin)//防止数组中全是相同的数，导致maxi没有改变
25.                 {
26.                         maxi = mini;
27.                 }
28.                 Swap(&arr[mini], &arr[begin]);//让最小的数与第一个数进行交换
29.                 Swap(&arr[maxi], &arr[end]);//让最大的数与第二个数进行交换
30.                 ++begin;//已经找到最小的数，需要找第二小的数，所以begin++
31.                 --end;//已经找到最大的数，需要找第二大的数，所以end--
32.         }
33. }

复制代码

3.冒泡排序（BubbleSort）

3.1 核心思绪

   冒泡排序的核心思绪是暴力比较，所有的数都比较一遍。
  

   例如上面的数组，将3与剩下所有的数字比较，3大于1，则把3放在1的位置，1放在3的位置。 所有的数比较完成后就能得到有序的数组。
  3.2 实现代码

1. void BubbleSort(int* arr, int n)
2. {
3.         for (int i = 0; i < n; i++)//找好第一个数
4.         {
5.                 for (int j = i + 1; j < n; j++)//从第二个数开始
6.                 {
7.                         if (arr[i] > arr[j])//所有的数与第一个数进行比较
8.                         {
9.                                 Swap(&arr[i], &arr[j]);
10.                                 //如果第一个数大于比较的数，则交换这两个数
11.                         }
12.                 }
13.         }
14. }

复制代码

4.希尔排序（ShellSort）

4.1 核心思绪

   希尔排序的核心思绪是将数组分成多少个小组，小组先辈行预排序，小组预排序完成后，再将 所有的组合并而且进行排序。
  

   例如上面的数组，将数组分成三分之一，则得到[3,6][7,1][4,2]三个数组。先对这三个数组进行排序，得到[3,6][1,7][2,4]三个数组。 然后将这三个数组合并成两个数组，得到[3,6,1][7,2,4]两个数组。再对[3,6,1][7,2,4]进行排序。得到[1,3,6][2,4,7]两个数组。 再将这两个数组合并，得到[1,3,6,2,4,7],排序得到[1,2,3,4,6,7]。
  4.2 实现代码

1. // 希尔排序
2. void ShellSort(int* arr, int n)
3. {
4.         int gap = n;
6.         while (gap > 1)
7.         {
8.                 gap = gap / 3 + 1;
9.                 //将数组分成三分之一。+ 1 是为了防止gap < 3从而导致gap / 3 == 0
10.                 //同时for循环结束时，再将数组进行细分
11.                 for (int i = 0; i < n - gap; i++)
12.                 //由于数组被分成三分之一个，所以数组的大小也变为三分之一
13.                 {
14.                         int end = i;
15.                         //第一个小组的第一个成员，i++之后就是第二个小组的第一个成员
16.                         int tmp = arr[end + gap];
17.                         //第一个小组的最后一个成员，i++之后就是第二个小组的最后一个成员
18.                         while (end >= 0)
19.                         //
20.                         {
21.                                 if (arr[end] > tmp)
22.                                 //当第一个小组里的第一个成员大于最后一个成员时
23.                                 {
24.                                         arr[end + gap] = arr[end];
25.                                         //把第一个成员放到最后一个成员的位置
26.                                         end -= gap;
27.                                         //由于开始比较的是所有组的第一个成员
28.                                         //当end > gap时，说明要开始比较组里的第二个成员了
29.                                         //第二个成员比较完，再比较第三个成员
30.                                 }
31.                                 else {
32.                                         break;
33.                                 }
34.                         }
35.                         arr[end + gap] = tmp;//有两种情况
36.                         //1.end减少到 < 0，说明这一组的数成倒序
37.                         //则需要把组里所有的数比较并交换完之后结束循环
38.                     //2.break提前跳出循环
39.                     //说明此时组里所有比end位置大的数均位于end + gap之后
40.                 }
41.         }
42. }

复制代码

  完


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