发布时间 : 星期日 文章各种排序算法总结汇编更新完毕开始阅读de358708aa114431b90d6c85ec3a87c240288a1d
学习-----好资料
各种排序算法总结
排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。 下面这个表格总结了各种排序算法的复杂度与稳定性：
各种排序算法复杂度比较.png 冒泡排序
冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。
算法原理
相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成 ? c++代码实现
?
1. void bubble_sort(int arr[], int len) 2. {
3. for (int i = 0; i < len - 1; i++) 4. {
5. for (int j = len - 1; j >= i; j--) 6. {
7. if (arr[j] < arr[j - 1]) 8. {
9. int temp = arr[j];
更多精品文档
学习-----好资料
10. arr[j] = arr[j - 1]; 11. arr[j - 1] = temp; 12. } 13. } 14. } 15. } 选择排序
算法原理
先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 ? c++代码实现
?
1. void select_sort(int arr[], int len) 2. {
3. for (int i = 0; i < len; i++) 4. {
5. int index = i;
6. for (int j = i + 1; j < len; j++) 7. {
8. if (arr[j] < arr[index]) 9. index = j; 10. }
11. if (index != i) 12. {
13. int temp = arr[i]; 14. arr[i] = arr[index]; 15. arr[index] = temp; 16. } 17. } 18. } 插入排序
算法原理
将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2) ? c++代码实现
?
1. void insert_sort(int arr[], int len) 2. {
更多精品文档
学习-----好资料
3. for (int i = 1; i < len; i ++) 4. {
5. int j = i - 1; 6. int k = arr[i];
7. while (j > -1 && k < arr[j] ) 8. {
9. arr[j + 1] = arr[j]; 10. j --; 11. }
12. arr[j + 1] = k; 13. } 14. } 快速排序
算法原理
快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 ? c++代码实现
?
1. void quick_sort(int arr[], int left, int right) 2. {
3. if (left < right) 4. {
5. int i = left, j = right, target = arr[left]; 6. while (i < j) 7. {
8. while (i < j && arr[j] > target) 9. j--;
10. if (i < j)
11. arr[i++] = arr[j]; 12.
13. while (i < j && arr[i] < target) 14. i++; 15. if (i < j)
16. arr[j] = arr[i]; 17. }
18. arr[i] = target;
19. quick_sort(arr, left, i - 1); 20. quick_sort(arr, i + 1, right); 21. }
更多精品文档
学习-----好资料
22. } 归并排序
?
算法原理
归并排序具体工作原理如下（假设序列共有n个元素）：
o 将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
o 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
o 重复步骤2，直到所有元素排序完毕
归并排序是稳定的排序算法，其时间复杂度为O(nlogn)，如果是使用链表的实现的话，空间复杂度可以达到O(1)，但如果是使用数组来存储数据的话，在归并的过程中，需要临时空间来存储归并好的数据，所以空间复杂度为O(n)
?
c++代码实现
1. void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index) 2. {
3. int i = start_index, j = mid_index + 1; 4. int k = 0;
5. while (i < mid_index + 1 && j < end_index + 1) 6. {
7. if (arr[i] > arr[j])
8. temp_arr[k++] = arr[j++]; 9. else
10. temp_arr[k++] = arr[i++]; 11. }
12. while (i < mid_index + 1) 13. {
14. temp_arr[k++] = arr[i++]; 15. }
16. while (j < end_index + 1)
17. temp_arr[k++] = arr[j++]; 18.
19. for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
20. arr[j] = temp_arr[i]; 21. } 22.
23. void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
更多精品文档