经典排序算法原理及稳定性判断_如何判断排序是否稳定

1. 冒泡排序

原理：

将n个记录看作按纵向排列，每趟排序时自下至上对每对相邻记录进行比较，若次序不符合要求（逆序）就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置，整个排序过程共进行n-1趟，依次将关键字最小、次小、第三小…的各个记录“冒到”表的第一个、第二个、第三个… 位置上。

例子

例子为从小到大排序,

原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |



第一趟排序(外循环)

第一次两两比较6 > 2交换(内循环)

交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |



第二次两两比较,6 > 4交换

交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |



第三次两两比较,6 > 1交换

交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |



第四次两两比较,6 > 5交换

交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |



第五次两两比较,6 < 9不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |



第二趟排序(外循环)

第一次两两比较2 < 4不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |



第二次两两比较,4 > 1交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |



第三次两两比较,4 < 5不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |



第四次两两比较,5 < 6不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |



第三趟排序(外循环)

第一次两两比较2 > 1交换

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |



第二次两两比较,2 < 4不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |



第三次两两比较,4 < 5不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |



第四趟排序(外循环)无交换

第五趟排序(外循环)无交换



排序完毕,输出最终结果1 2 4 5 6 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

稳定性判断：

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个
元素比较，交换也发生在这两个元素之间。

    所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变.

    所以冒泡排序是一种稳定排序算法。
1
2
3
4
5
6

2. 选择排序

原理：

  顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完。

  再简单点,对着一群数组说,你们谁最小出列,站到最后边,然后继续对剩余的无序数组说,你们谁最小出列,站到最后边,再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了,从小到大。

例子

先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]

第一趟找到最小数1,放到最前边(与首位数字交换)

交换前:| 6 | 2 | 4 | 1 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位

交换前:| 1 | 2 | 4 | 6 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |



第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换

第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置

交换前:| 1 | 2 | 4 | 6 | 5 | 9 |

交换后:| 1 | 2 | 4 | 5 | 6 | 9 |

第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换

排序完毕输出正确结果[1 2 4 5 6 9]

           下面是找出最小数的算法：

第一趟找到最小数1的细节

当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |

先把6取出来,让它扮演最小数

当前最小数6与其它数一一进行比较,发现更小数就交换角色

当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较

当前最小数2与4比较,不动

当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较

当前最小数1与5比较,不动

当前最小数1与9比较,不动,到达末尾

当前最小数1与当前首位数字进行位置交换,如下所示

交换前:| 6 | 2 | 4 | 1 | 5 | 9 |

交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

完成一趟排序,其余步骤类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

稳定性判断：

    选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

    比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
1
2
3

3. 插入排序

原理：

  插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

  插入排序方法分直接插入排序和折半插入排序两种。

  折半插入排序基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序采用折半查找法来寻找插入位置。折半查找法只能对有序的序列使用。基本思想就是查找插入位置的时候，把序列分成两半（选择一个中间数mid），如果带插入数据大于mid则到右半部分序列去在进行折半查找；反之，则到左半部分序列去折半查找。

例子

设数组为a[0…n-1]。

1.      初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2.      将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3.      i++并重复第二步直到i==n-1。排序完成。
1
2
3
4
5
6
7

稳定性判断：

    插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。
    比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
    如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序。
    所以插入排序是稳定的。
1
2
3
4

4. 快速排序

原理：

通过一趟扫描将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

例子

如无序数组[6 2 4 1 5 9]

a),先把第一项[6]取出来,

用[6]依次与其余项进行比较,

如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边

如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~

一趟排完后变成下边这样:

排序前 6 2 4 1 5 9

排序后 2 4 1 5 6 9



b),对前半拉[2 4 1 5]继续进行快速排序

重复步骤a)后变成下边这样:

排序前 2 4 1 5

排序后 1 2 4 5

前半拉排序完成,总的排序也完成:

排序前:[6 2 4 1 5 9]

排序后:[1 2 4 5 6 9]

排序结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

稳定性判断：

    快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，
     其中center_index是中枢元素的数组下标，一般取为数组第0
1
2