算法学习-排序

风尘

文章目录

  1. 1. 排序稳定性
  2. 2. 冒泡排序
    1. 2.1. 时间复杂度
    2. 2.2. 空间复杂度
    3. 2.3. 稳定性
  3. 3. 选择排序
    1. 3.1. 时间复杂度
    2. 3.2. 稳定性
  4. 4. 插入排序
    1. 4.1. 时间复杂度
    2. 4.2. 空间复杂度
    3. 4.3. 稳定性
  5. 5. 希尔排序
    1. 5.1. 时间复杂度
    2. 5.2. 稳定性
  6. 6. 归并排序
    1. 6.1. 时间复杂度
    2. 6.2. 稳定性
  7. 7. 快速排序
    1. 7.1. 时间复杂度
    2. 7.2. 稳定性

排序稳定性

已知序列 r,排序前 rir_i 领先于 rjr_ji<ji<j)。当排序后 rir_i 仍领先于 rjr_j,则所用排序方法是稳定的;反之,则称排序方法不稳定

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的数列,每次两两比较相邻记录,如果第一个元素比第二个元素大,则交换他们位置。同理继续比较第二个与第三个元素,重复这个操作直到所有最大元素排到最右侧为止。
冒泡排序示意图冒泡排序示意图

代码实现
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
/**
* 冒泡排序
* @param nums 序列
* @param numsSize 序列大小
*/
int *bubbleSort(int *nums, int numsSize) {
int *newNums = nums;
if (nums) {
int i, j;

printNums(nums, numsSize);
boolean flag = TRUE; // 当序列前面元素都小于后面元素时说明排序已完成,不需要进行无意义的循环,所以增加 flag 标识结束循环操作
for (i = 0; i < numsSize - 1 && flag; i++) { // 倒数第二次比较就可以完成所有排序,所以用i < numsSize - 1 代替 i < numsSize 可以少循环一次
flag = FALSE;
for (j = 0; j < numsSize - i - 1; j++) { // i < numsSize - i - 1 是因为 j 要与 j + 1 比较
if (newNums[j] > newNums[j + 1]) {
int temp = newNums[j + 1];
newNums[j + 1] = newNums[j];
newNums[j] = temp;
flag = TRUE;
printNums(nums, numsSize);
}
}
}
}

return newNums;
}

时间复杂度

最好的情况,序列本身是有序的,可以推断出算法进行 n1n-1 次比较,没有数据交换,时间复杂度为 O(n)O(n)
最坏的情况,序列本身是逆序的,当:
i=2i=2 时,比较 11
i=3i=3 时,比较 22

i=ni=n 时,比较 n1n-1
总共比较了

T(n)=i=2n(i1)=1+2+3+...+(n1)=(1+n1)(n1)2=n(n1)2=12n212nT(n)=\sum^{n}_{i=2}(i-1)=1+2+3+...+(n-1)=\frac{(1+n-1)(n-1)}{2}=\frac{n(n-1)}{2}=\frac{1}{2}n^2-\frac{1}{2}n

次,根据复杂度推导原则,去掉常数和最高项等其复杂度为 O(n2)O(n^2)

空间复杂度

空间很杂度就是在交换元素时 temp 临时变量所占的内存空间。
最好情况,是序列已排好序,则空间复杂度为 0;
最坏情况,是序列本身逆序,则空间复杂度为 O(n)O(n)
所以算法平均空间复杂度为 O(1)O(1)

稳定性

冒泡排序是稳定的原地排序算法。

选择排序

选择排序的原理是,先从给定序列中选出一个最小元素 min (通常是无序区间第一个元素),然后与后面元素进行比较,选出最小元素与之交换,min 位置前面就变成了有序区间,min 位置后面则是无序区间,继续在无序区间重复前面操作直到全部变成有序区间后,排序完成。

选择排序示意图选择排序示意图
代码实现
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
/**
* 选择排序(每次找出最小元素与数组第一个元素交换)
* @param nums 序列
* @param numsSize 序列大小
*/
int *chooseSort(int *nums, int numsSize) {
int *newNums = nums;

if (newNums) {
int i, j;

for (i = 0; i < numsSize; i++) {
int temp;
int min = i;

for (j = i + 1; j < numsSize; j++) {
if (newNums[j] < newNums[min]) min = j;
}

temp = newNums[i];
newNums[i] = newNums[min];
newNums[min] = temp;
}
}

return newNums;
}

时间复杂度

该算法最大特点就是交换移动数据次数很少,可以节约相应时间。但是它的比较次数无论是最好或最差情况下都是一样多,当
i=0i=0 时,比较 n1n-1
i=1i=1 时,比较 n2n-2 次 

i=n2i=n-2 时,比较 11 次 
总共比较了

T(n)=i=1n1(ni)=(n1)+(n2)+...+2+1=n(n1)2=12n212nT(n)=\sum^{n-1}_{i=1}(n-i)=(n-1)+(n-2)+...+2+1=\frac{n(n-1)}{2}=\frac{1}{2}n^2-\frac{1}{2}n

次,根据复杂度推导原则,去掉常数和最高项等其复杂度为 O(n2)O(n^2)

稳定性

由于选择元素之后发生交换操作,所以很可能把前面元素交换到后面,所以该排序算法是不稳定的。

插入排序

插入排序采用in-place在数组上实现的算法,
具体步骤是

  1. 从第一个元素开始,认为该元素是有序序列,取出下一个元素作为临时元素,在有序序列中从后向前逐一比较。
  2. 如果有序序列中元素大于临时元素,则将该元素向后移动一位。
  3. 如果该元素小于等于临时元素,则将临时元素插入到该位置,此时有序序列长度增加一。
  4. 临时元素索引加一继续作为临时元素,重复前面步骤,直到临时元素索引超出序列长度,排序完成。
插入排序示意图插入排序示意图
代码实现
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
/**
* 插入排序
* @param nums 序列
* @param numsSize 序列大小
*/
int *insertSort(int *nums, int numsSize) {
int *newNums = nums;

if (newNums) {
int i, j;
for (i = 1; i < numsSize; i++) {
if (newNums[i - 1] > newNums[i]) {
int temp = newNums[i];

for (j = i - 1; j >= 0 && newNums[j] > temp; j--) {
newNums[j + 1] = newNums[j];
}

newNums[j + 1] = temp;
}
}
}

return newNums;
}

时间复杂度

对于 n 个元素,外层循环执行T(n)=n1T(n)=n-1 次,内层循环,当:
i=1i=1 时,执行 11
i=2i=2 时,执行 22

i=n1i=n-1 时,执行 n1n-1
总共执行了

T(n)=i=1n1i=1+2+...+(n1)=n(n1)2=12n212nT(n)=\sum^{n-1}_{i=1}i=1+2+...+(n-1)=\frac{n(n-1)}{2}=\frac{1}{2}n^2-\frac{1}{2}n

次,根据复杂度推导原则,去掉常数和最高项等其复杂度为 O(n2)O(n^2)

空间复杂度

插入排序通常采用in-place排序,所以空间复杂度为 O(1)O(1)

稳定性

因为排序比较时,当两个数相等时,不会进行移动,因此前后次序不会发生变化,所以该排序算法是稳定的。

希尔排序

希尔排序是 D.L.Shell 于 1959 年提出的一种排序算法,之前排序算法时间复杂度基本都是 O(n2)O(n^2),希尔排序是突破这个时间复杂度的第一批算法之一。

插入排序通常在小规模数据或是序列基本有序时十分高效,但是满足这两个条件是比较困难。希尔排序就是对插入排序的改进算法,
基本思路是

  • 将原有大量记录序列进行分组,侵割成若干个子序列。
  • 在这些子序列内分别进行直接插入排序,当整个序列都基本有序时,再对整个序列进行一次直接插入排序,完成排序。

所谓基本有序,指的是序列中较小元素基本在前面,较大元素基本在后面,不大不小元素基本在中间,如:2,1,3,6,4,7,5,8,9{2, 1, 3, 6, 4, 7, 5, 8, 9}
为了使整个序列基本有序,采取跳跃分割策略,将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列排序后整个序列基本有序,而不是局部有序

步骤
以增加 gap=length/2=4gap=length/2=4 方式计算,首先将序列可逻辑分成四组子序列 [5,1][5,1][7,2][7,2][8,4][8,4][3,6][3,6],如下:
希尔排序分组示意图希尔排序分组示意图

分别对各个子序列进行插入排序可得到逻辑子序列分别为 [1,5][1,5][2,7][2,7][4,8][4,8][3,6][3,6] 总序列为 [1,2,4,3,5,7,8,6][1,2,4,3,5,7,8,6],如图:
希尔排序子序列排序示意图希尔排序子序列排序示意图

然后继续以 gap=gap/2gap=gap/2 && gap>0gap>0 方式计算,重复上述步骤。
最后根据得到的基本有序序列再一次进入直接插入排序,最终完成排序。

示例代码
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
/**
* 希尔排序
* @param nums 序列
* @param numSize 序列大小
* @return
*/
int *shellSort(int *nums, int numsSize) {
int *newNums = nums;

if (newNums) {
for (int gap = numsSize / 2; gap > 0; gap /= 2) {
for (int i = gap; i < numsSize; i++) {
if (newNums[i - gap] > newNums[i]) {
int j;
int temp = newNums[i];

for (j = i - gap; j >= 0 && newNums[j] > temp; j -= gap) {
newNums[j + gap] = newNums[j];
}

newNums[j + gap] = temp;
}
}
}

}

return newNums;
}

时间复杂度

希尔排序算法的时间复杂度与其增量gap设置有关,迄今为止还没有能证明出来的增量序列,不过有实验表明当增量序列为 2k12^k-1 时,时间复杂度最坏情况为 O(n1.5)O(n^{1.5})

稳定性

虽然插入排序是稳定的,但是希尔排序在插入的时候是跳跃性插入的,有可能破坏其稳定性,所以希尔排序是不稳定的。

归并排序

归并排序(Merging Sort) 就是将待排序的数分成两半后排好序,然后再将两个排好序的序列合并成一个有序序列。 归并排序是一个比较占用内存,但效率高的算法。
基本原理是
将有n 个元素的序列看成是n 个有序的子序列,每个子序列长度为1(一个元素认为它有序的), 然后两两归并,…重复归并,直至得到一个长度为n 的有序序列为止,这种方法称为2路归并法

归并排序示意图归并排序示意图
递归实现示例代码
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
/**
* 归并排序
* @param nums 序列
* @param numSize 序列大小
* @return
*/
int *mergeSort(int *nums, int numSize) {
int *newNums = nums;

if (newNums) {
mSort(newNums, 0, numSize - 1);
}

return newNums;
}

void mSort(int *newNums, int left, int right) {
if (left < right) {
// 将序列一分为二
int center = (left + right) / 2;

// 排序左边数组
mSort(newNums, left, center);
// 排序右边数组
mSort(newNums, center + 1, right);
// 合并两个序列
mSortMerge(newNums, left, center, right);
}
}

void mSortMerge(int *newNums, int left, int center, int right) {
int i = left;
int j = center + 1;
int *tempNums = malloc(sizeof(newNums));

for (int k = left; k <= right; k++) {
// j > right 时,表示右子序列元素全部放入到了临时数组(tempNums) 中,此时只剩下左子序列有元素,由于单侧子序列都是有序的,所以直接将左子序列元素顺序放入临时数组(tempNums)中即可。
// 反之,当 j <= right 且 i > center 时,表示左子序列元素全部放入到了临时数组中,此时只剩下右子序列有元素,所以直接将右子序列元素顺序放入临时数组中即可。
// 该操作通过递归函数重复调用直到排序完成为止
if (j > right || newNums[i] <= newNums[j])
tempNums[k] = newNums[i++];
else
tempNums[k] = newNums[j++];
}

// 将排好序的临时数组元素复制到原数组中
for (int k = left; k <= right; k++) {
newNums[k] = tempNums[k];
}

free(tempNums);
}

递归实现的执行步骤如下

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
排序序列:5	4	3	2	1
------------------------------
L->C->R:0 2 4
分割序列:5 4 3 2 1
------------------------------
L->C->R:0 1 2
分割序列:5 4 3
------------------------------
L->C->R:0 0 1
分割序列:5 4
------------------------------
L->C->R:0 0 1
待排序序列:5 4
序列中较小元素:4
序列中较小元素:5
排序完成序列:4 5
------------------------------
L->C->R:0 1 2
待排序序列:4 5 3
序列中较小元素:3
序列中较小元素:4
序列中较小元素:5
排序完成序列:3 4 5
------------------------------
L->C->R:3 3 4
分割序列:3 4
------------------------------
L->C->R:3 3 4
待排序序列:3 4
序列中较小元素:1
序列中较小元素:2
排序完成序列:3 4 5 1 2
------------------------------
L->C->R:0 2 4
待排序序列:3 4 5 1 2
序列中较小元素:1
序列中较小元素:2
序列中较小元素:3
序列中较小元素:4
序列中较小元素:5
排序完成序列:1 2 3 4 5
归并排序(非递归实现)
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
/**
* 归并排序(非递归实现)
* 实现原理:首先将序列中每个元素作为子序列,把相临子序列两两配对排序;
* 然后,再将两个排好序的子序列作为一个子序列,再对相临子序列进行排序,重复上面步骤直到排序完成
* @param nums 序列
* ‧param numSize 序列大小
*/
int *mergeSortNonRecursive(int *nums, int numSize) {
int *newNums = nums;

if (newNums) {
// 定义子序列的大小分别为 1、2、4、8...逐渐递增
for (int i = 1; i < numSize; i += i) {
int left = 0;
int center = left + i - 1;
int right = center + i;

// 对子序列时行两两合并
while (right < numSize) {
// 合并两序列
mSortMerge(newNums, left, center, right);
left = right + 1;
center = left + i - 1;
right = center + i;
}

// 因为不可能每个子序列的大小都刚好为
// i,所以可能存在遗漏元素没有合并,因此最后要对遗漏元素进行合并
if (left < numSize && center < numSize) {
mSortMerge(newNums, left, center, numSize - 1);
}
}
}

return newNums;
}

时间复杂度

由于归并排序数据结构属于完全二杈树,而由完全二杈树的深度可知 T(n)=log2nT(n)=log_2n 次。排序最后要将临时数组元素复制到原数组中,此时 T(n)=O(n)T(n)=O(n) 次。因此,总时间复杂度为 O(nlogn)O(nlogn)

稳定性

归并排序中不存在跳跃,只有两两比较,因此是一种稳定排序。

快速排序

所谓快速排序,也是一种采用分治思想的排序方法,其基本思路是
首先,在要排序的序列(nums)中任意选取一个元素(通常选择第一个元素),该元素被称为中枢元素。然后根据中枢元素进行排序,将小于等于中枢元素的元素放在中枢元素的左边,将大于等于中枢元素的元素放在中枢元素的右边。然后再把序列根据中枢元素位置(pivot)分割成两个子序列,即左子序列(nums[low,pivot-1]) 和右子序列(nums[pivot+1,high]),继续重复前面步骤直到整个序列有序。

快速排序示意图快速排序示意图

上面整个排序过程的主要目的是选出中枢元素,然后将中枢元素交换到有序位置(即中枢元素大于其左侧所有元素,小于其右侧所有元素),然后再将序列分割成左、右子序列,分别在两个序列中选出中枢元素继续交换到有序位置,直到序列大小最终被分割为 1 为止(当序列只有 1 个元素时,即可认为该序列有序)。

示例代码
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
/**
* 快速排序
* @param nums 序列
* @param numsSize 序列大小
* @date 2020-03-30 16:47
* @author Windus
*/
int *quickSort(int *nums, int numsSize) {
int *newNums = nums;

if (newNums) {
void qSortRecursion(int *nums, int low, int high);
qSortRecursion(newNums, 0, numsSize - 1);
}

return newNums;
}

void qSortRecursion(int *nums, int low, int high) {
if (low < high) {
int partition(int *nums, int low, int high);
// 获取中枢元素,并根据中枢将子序列排序
int pivot = partition(nums, low, high);

// 对左子序列进行排序
qSortRecursion(nums, low, pivot - 1);

// 对右子序列进行排序
qSortRecursion(nums, pivot + 1, high);
}
}

int partition(int *nums, int low, int high) {
int temp;
int pivot = low;

while (low < high) {
// 从左向右扫描比中枢元素大的元素
while (low < high && nums[low] <= nums[high]) low++;
// 从右向左扫描比中枢元素小的元素
while (low < high && nums[high] >= nums[pivot]) high--;

// 当左侧指针位置大于或等于右侧指针时,跳出循环,不进行左右元素交换(因为左指针元素已经小于等于中枢元素,不需要移动位置了)
if (low >= high) break;

// 交换两指针元素元素,使左指针元素小于右指针元素
temp = nums[high];
nums[high] = nums[low];
nums[low] = temp;
}

// 交换中枢元素,使中枢元素处于有序位置
temp = nums[high];
nums[high] = nums[pivot];
nums[pivot] = temp;

return pivot;
}

中枢元素的选取直接影响快速排序性能,当中枢元素处于整个序列中间位置时最优,但在现实中,待排序序列极有可能是基本有序的,此时,如果固定选取某一元素作为中枢元素并不是好的排序办法。因此可以通过随机或取中间数的方法来选取中枢元素。

三数取中选取中枢元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pivot;

// 计算中间元素的下标
int m = (high - low) / 2;

if(nums[low] > nums[high])
swap(nums, low, high); // 交换左、右两侧元素,保证左侧元素较小
if(nums[m] > nums[high])
swap(nums, high, m); // 交换中间与右侧元素,保证中间较小
if(nums[m] > nums[low])
swap(nums, m, low); // 交换中间与左侧元素,保证左侧元素较小

/* 此时 nums[low] 已经成为三个元素的中间值,用于当作中枢元素 */
pivot = low;

时间复杂度

虽然快速排序的平均时间复杂度也是O(nlogn)O(nlogn),但是不需要像归并排序那样,需要一个临时数组辅助排序,这样可以节省掉一些空间消耗。同时也不需要像归并排序那样,把两部分有序子序列汇总到临时数组之后,再复制回源数组 ,这样也可以节省很多时间。

稳定性

该排序是不稳定的,因为在整个序列扫描时,中枢元素与 high 位置发生交换的时候,可能破坏其稳定性。