【C++算法】几种排序算法

标题

排序标题： 给定⼀个⽆序序列，采⽤以下排序⽅法分别对序列升序排序，并编程⽐较各种排序算法的性能。
(1) 插⼊排序；
(2) 选择排序；
(3) 归并排序；

分析

本题要我们比力插入排序，选择排序，归并排序三种排序的算法性能，那么我们起首要搞懂这三种排序的实现方式。
      

       起首是插入排序，如其名字一样，他就是将数组内的每个元素一个个的往前移，插入到前面已经排好序的数组内里。详细实现过程就是，先默认第一个元素已经排好序了，然后将第一个元素后面第一个元素往前搜刮，找到属于它的位置后，将第一个元素今后移一位，给这个元素的插入腾位置，这样前两天元素就是一个有序数列，后面就到了前移第三个元素，也是将第三个元素往前搜刮，找到属于它的位置后就把它后面的有序数列的元素后移一位给它腾位置，直到所有的元素都被插入到有序数列中去后，这整个序列就变成了一个有序数列，这就是插入排序。

       第二个是选择排序，选择排序和插入排序相反，它是向后搜刮，也就是搜刮整个还未被排列的数组，选择一个最小的元素放到有序数组的末端，直到未被排列的数组元素个数为0时，就代表所有的元素都被选择过了，都已经被放进了有序数组内。详细来说，就是先从第一个位置开始，搜刮后面的整个数组，找到一个最小的元素放到第一个位置，然后就进入到下一次循环，从第二个位置开始，搜刮后面的整个数组，找到一个最小的元素（在整个数组中这个元素是第二小的，但是未被排序的数组中这个元素是最小的），把这个元素放到第二个位置上，直到所有的元素都被选择过后，就完成了选择排序。

       第三个是归并排序，归并排序着实用到了分治算法的思想，将对多个元素排序这个大标题拆分成了对多个只有两个元素的数组排序后，在合并所有的两元素数组。详细来说，就是先用二分法递归拆分整个数组，然后两两一对按照升序组成一个数组，之后再合并两个两元素的数组，采用双指针分别从两个数组的第一个元素开始遍历，谁小就先将谁放到新数组内里去，直到指针指向了末了一个元素的后一个位置，这样就合并好了一个两元素数组，直到所有两元素数组都被合并后（假如是奇数个末了一个两元素数组不用管，让他下一次合并再合并就行了），后面就按照相同的方法两两合并四元素数组就行了，直到所有数组都被合并后，形成的新数组就是有序数组，至此完成了归并排序。
       至此我们已经理解了三个排序的排序过程和代码写法，下面我们分析一下这三种排序的性能：
       从时间复杂度上分析，插入排序必要一次循环把所有的元素前插到数组前面去，一次循环寻找插入的位置，所以时间复杂度为O(n^2)。选择排序则还必要一层循环将中间的元素后移，所以有两层循环，时间复杂度为O(n^2)。归并排序涉及到二分递归，根据master定理假设递归次数和递推关系式，得时间复杂度为O(nlogn)，由此可见，在数组规模不大的时候，三者的运行时间着实不会差许多，当数组轻微大一点后，选择排序的运行时间会远超插入排序和归并排序，因为插入排序可能只必要遍历一次就可以排好序，所以最好时间复杂度是O(n)，总体来看会比选择排序快。
       从空间复杂度来看，选择排序和插入排序的排序过程都只用到了一般变量，而归并排序的过程必要用到数组，所以选择排序和插入排序的时间复杂度为O(n)，归并排序的时间复杂度为O(n^2)。
       从稳定性来看，三个排序的排序过程都是严格按照原数组的元素次序进行选择或二分的，故排序效果都是稳定的。
       而判定三者的性能，我们可以通过盘算机“time.h”包内的clock()函数进行计时，判定三个排序方式的排序时间。

代码和运行效果

1. # include <bits/stdc++.h>
2. # include "time.h"
3. using namespace std;
5. //插入排序
6. void InsertSort1(int *a, int n)
7. {
8.         int i, j;
9.         for (i = 1; i < n; i++)//默认第一个元素以排序，从第二个开始（即使第一个不是最小的，后面也会让这个元素往后移的）
10.                 if (a[i] < a[i - 1])
11.                 {
12.                         int temp = a[i];                       //保存要比较的值
13.                         for (j = i - 1; j >= 0 && a[j] > temp; j--)    //以选择元素为起始点，从后向前查找待插入位置
14.                                 a[j + 1] = a[j];                    
15.                         a[j + 1] = temp;                       
16.                 }
17.         for (int i = 0;i < 20;i++)
18.                 cout << a[i] << " ";
19.         cout << endl;
20. }
22. //选择排序
23. void SelectSort(int *a, int n)
24. {
25.         int i, j, min, t;
26.         for (i = 0;i < n - 1;i++)  //这个for循环是排序次数，n个数只需要排序n-1次，最后只剩一个数不需要排序
27.         {
28.                 min = i;
29.                 for (j = i + 1;j < n;j++)  //这个for循环是寻找下标为i的元素后面有没有比它更小的数
30.                 {
31.                         if (a[j] < a[min])  
32.                                 min = j;
33.                 }
34.                 if (min != i)   
35.                 {
36.                         t = a[i];     
37.                         a[i] = a[min];
38.                         a[min] = t;
39.                 }
40.         }
41.         for (int i = 0;i < 20;i++)
42.                 cout << a[i] << " ";
43.         cout << endl;
44. }
46. void Merge(int A[], int Temp[], int L, int R, int RightEnd)
47. {
48.         int LeftEnd = R - 1;
49.         int p = L, i;
50.         int num = RightEnd - L + 1;
52.         //先合并最短序列的长度的个数个元素
53.         while (L <= LeftEnd && R <= RightEnd)
54.         { //这个循环执行完左数组和右数组一定有一个已经被搬空到temp中去了
55.                 if (A[L] <= A[R])
56.                         Temp[p++] = A[L++];
57.                 else
58.                         Temp[p++] = A[R++];
59.         }
60.         while (L <= LeftEnd)
61.                 Temp[p++] = A[L++];
62.         //判断如果是右侧数组还有剩余
63.         while (R <= RightEnd)
64.                 Temp[p++] = A[R++];
65.         // 将辅助空间中的值拷贝到原列表中，完成排序
66.         for (i = 0;i < num;i++, RightEnd--) //要从RightEnd开始赋值，因为不是每次排序的数组都是从0下标开始的，而L又被改过了，所以只能从RightEnd开始赋值
67.                 A[RightEnd] = Temp[RightEnd];
68. }
71. //递归拆分m_sort，递归归并Merge
72. void m_sort(int arr[], int* temp, int L, int right_end)
73. {
74.         int center;
75.         if (L < right_end)
76.         {
77.                 center = (L + right_end) / 2;
78.                 m_sort(arr, temp, L, center);
79.                 m_sort(arr, temp, center + 1, right_end);
80.                 Merge(arr, temp, L, center + 1, right_end);
81.         }                                                                                
82. }                                                                                       
84. //归并排序
85. void merge_Sort(int arr[], int length)
86. {
87.         int* temp = (int*)malloc(length * sizeof(int));   
88.         if (temp == NULL) {                              
89.                 return;
90.         }
91.         m_sort(arr, temp, 0, length - 1);      //发送待排序数组，辅助数组，最左边元素下标，最右边元素下标
92.         for (int i = 0;i < 20;i++)
93.                 cout << arr[i] << " ";
94.         cout << endl;
95.         free(temp);               
96.         temp = NULL;      
97. }
99. int main(void)
100. {
101.         int arr1[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
102.         int arr2[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
103.         int arr3[20] = { 3,5,2,10,8,9,6,4,7,1,6,7,8,9,5,4,3,2,1,8 };
104.         clock_t beg, end;
105.         beg = clock();
106.         merge_Sort(arr3, 20);
107.         end = clock();
108.         double time = (double)(end - beg) / CLOCKS_PER_SEC;
109.         cout << "归并排序运行时间为";
110.         printf("%lf\n", time);
111.         beg = clock();
112.         SelectSort(arr2, 20);
113.         end = clock();
114.         time = (double)(end - beg) / CLOCKS_PER_SEC;
115.         cout << "选择排序运行时间为";
116.         printf("%lf\n", time);
117.         beg = clock();
118.         InsertSort1(arr1, 20);
119.         end = clock();
120.         time = (double)(end - beg) / CLOCKS_PER_SEC;
121.         cout << "插入排序运行时间为";
122.         printf("%lf\n", time);
123.        
125.         return 0;
126. }

复制代码

        三种排序方式的各有各的优点，插入排序的有点在于快，在处理数组较小的环境下运行速度很快；而选择排序则更偏向于我们人一般的排序方法，比力简单易懂；归并排序在遇到数组较大的环境运行速度则会明显快于其他两个排序。

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