三种稳定的排序算法详解

易团雪

一.冒泡算法
比较相邻元素，符合比较条件，交换位置较大的往后排，反复比较交换，直到所有数据都符合排序条件，得出排序效果，结束排序
算法说明
1.比较相邻元素： 从数组的第一个元素开始，比较相邻的两个元素。
2.交换元素位置： 如果顺序不对（比如，当前元素大于下一个元素），就交换这两个元素的位置。
3.一轮过后的效果： 一轮过后，最大（或最小）的元素就会“冒泡”到数组的末尾。
4.重复进行多轮： 重复以上步骤，每轮都会使数组变得有序，并且确定一个元素的最终位置，直到整个数组有序

1. 函数 空类型 数组排序_冒泡算法(动态数组<整型> &需排序数组)
   
2. {
   
3.         逻辑型 是否交换
   
4.         整型 数组大小 = 需排序数组.取大小()
   
5.         变量循环 (整型 i = 0; i < 数组大小 - 1; i++)
   
6.         {
   
7.                 是否交换 = 假
   
8.                 变量循环 (整型 j = 0; j < 数组大小 - i - 1; j++)
   
9.                 {
   
10.                         如果 (需排序数组[j] > 需排序数组[j + 1])
    
11.                         {
    
12.                                 // 交换元素
    
13.                                 交换变量(需排序数组[j], 需排序数组[j + 1])
    
14.                                 是否交换 = 真
    
15.                         }
    
16.                 }
    
17.                 // 如果没有发生交换，数组已经有序，提前结束
    
18.                 如果 (!是否交换)
    
19.                 {
    
20.                         跳出
    
21.                 }
    
22.         }
    
23. }

复制代码

二.插入排序
插入排序得比喻成斗地主，手里摸牌之后都是按照从小到大的顺序。每摸到一张牌就把他们插入到合适的位置，使得他们比后面小，比前面大或者相等
算法说明
1.初始状态：将整个数组看作两个部分，已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含除第一个元素外的所有元素。
2.逐个插入：从未排序部分取出一个元素，将其插入到已排序部分的正确位置，使得插入后的序列仍然有序。
3.重复过程：重复上述步骤，每次从未排序部分取出一个元素并插入到已排序部分，直到整个数组有序。

1. 函数 空类型 数组排序_插入排序(动态数组<整型> &需排序数组)
   
2. {
   
3.         整型 temp
   
4.         变量循环 (整型 i = 1; i < 需排序数组.取大小(); i++)
   
5.         {
   
6.                 变量循环 (整型 j = i - 1; j >= 0; j--)
   
7.                 {
   
8.                         如果 (需排序数组[j + 1] < 需排序数组[j])
   
9.                         {
   
10.                                 temp = 需排序数组[j + 1]
    
11.                                 需排序数组[j + 1] = 需排序数组[j]
    
12.                                 需排序数组[j] = temp
    
13.                         }
    
14.                         否则 (需排序数组[j + 1] >= 需排序数组[j])
    
15.                         {
    
16.                                 跳出
    
17.                         }
    
18.                 }
    
19.         }
    
20. }

复制代码

三.归并排序
将长的数组分解为短的数组，一直分到最后，单个单个数组比较，我们就认为，只有一个元素的数组是有序的。然后再逐个的合并
算法说明
1.拆分（分治）： 将数组拆分为两半，然后对每一半递归地应用归并排序，直到每个子数组都只包含一个元素。
2.合并： 将已排序的两个子数组合并成一个有序数组。合并过程中，比较两个子数组的元素，将较小的元素放入新数组，并移动相应的指针。
3.递归： 递归地对子数组进行拆分和合并，直到整个数组有序。

1. 函数 空类型 归并排序_合并(动态数组<整型> &arr, 整型 low, 整型 mid, 整型 high)
   
2. {
   
3.         整型 n1 = mid - low + 1
   
4.         整型 n2 = high - mid
   
5.         // 创建临时数组
   
6.         动态数组<整型> left(n1)
   
7.         动态数组<整型> right(n2)
   
8.         // 将数据复制到临时数组 left[] 和 right[]
   
9.         变量循环 (整型 i = 0; i < n1; i++)
   
10.         {
    
11.                 left[i] = arr[low + i]
    
12.         }
    
13.         变量循环 (整型 j = 0; j < n2; j++)
    
14.         {
    
15.                 right[j] = arr[mid + 1 + j]
    
16.         }
    
17.         // 合并临时数组 back 到 arr[low..high]
    
18.         整型 i = 0  // 初始左半部分的索引
    
19.         整型 j = 0  // 初始右半部分的索引
    
20.         整型 k = low  // 初始合并数组的索引
    
21.         循环 (i < n1 && j < n2)
    
22.         {
    
23.                 如果 (left[i] <= right[j])
    
24.                 {
    
25.                         arr[k] = left[i]
    
26.                         i++
    
27.                 }
    
28.                 否则
    
29.                 {
    
30.                         arr[k] = right[j]
    
31.                         j++
    
32.                 }
    
33.                 k++
    
34.         }
    
35.         // 复制剩余的元素（如果有的话）
    
36.         循环 (i < n1)
    
37.         {
    
38.                 arr[k] = left[i]
    
39.                 i++
    
40.                 k++
    
41.         }
    
42.         循环 (j < n2)
    
43.         {
    
44.                 arr[k] = right[j]
    
45.                 j++
    
46.                 k++
    
47.         }
    
48. }
    
49. 函数 空类型 数组排序_递归(动态数组<整型> &arr, 整型 low, 整型 high)
    
50. {
    
51.         如果 (low < high)
    
52.         {
    
53.                 // 计算中间位置
    
54.                 整型 mid = low + (high - low) / 2
    
55.                 // 递归排序左右两侧
    
56.                 数组排序_递归(arr, low, mid)
    
57.                 数组排序_递归(arr, mid + 1, high)
    
58.                 // 合并两个已排序的部分
    
59.                 归并排序_合并(arr, low, mid, high)
    
60.         }
    
61. }

复制代码

以上来源于网络,我只是翻译

呵呵仙

谢谢,学习了!

admin

感谢大佬分享

misou

支持大佬，学习了。