Fork me on GitHub

常见排序算法

常见排序算法

排序算法中几个概念

  1. 稳定性:两个相等的数在排序前后”相对位置”不变,则算法稳定。
    稳定性得好处:从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

  2. 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
    T(n) = O(f(n)) // n 计算次数

  3. 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。
    S(n) = O(f(n))

    各种算法稳定性

    1、堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法;
    2、基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

1. 选择排序

算法描述:在未排序序列中找到最小(大)元素,将其存放到排序序列的起始位置,然后从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾,

该算法在给定的数组中维护了连个子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
int temp = a[minIndex];
a[minIndex] = a[i];
a[i] = temp;
}
}

时间复杂:O(n^2)
空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void selectionSortStable(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
int minimum = a[minIndex];
while (minIndex > i) {
a[minIndex] = a[minIndex - 1];
minIndex--;
}
a[i] = minimum;
}
}

2. 冒泡排序

算法描述:冒泡排序是最简单的排序算法,如果它们的顺序错误,可以反复交换相邻的元素,重复进行直到没有交换。

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

时间复杂:O(n^2)
空间复杂度:O(1)
上面实现 时间复杂度始终是 O(n^2)
其实当没有元素进行交互,说明已是有序数组,可以及时跳出循环。
递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSortRecursive(int[] a, int n) {
if (1 == n) {
return;
}
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
bubbleSortRecursive(a, n - 1);
}

3. 插入排序

算法描述:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
int current = a[i]; // 当前选中元素
int j = i - 1; // 前一个元素下标
a[j + 1] = a[j];
j--;
}
a[j + 1] = current;
}
}

4. 归并排序

算法描述:该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

详细分解:把长度为n的输入序列分成两个长度为n/2的子序列;
对这两个子序列分别采用归排序;
将两个排序好的子序列合并成一个最终的排序序列。

图解如下:

sort_merge

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
	void mergeSort(int[] a, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}

void merge(int[] a, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
/* 创建左右零时数组 */
int L[] = new int[n1];
int R[] = new int[n2];
/*将数组左右部分拷贝到零时数组*/
for (int i = 0; i < n1; ++i) {
L[i] = a[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = a[m + 1 + j];
}
int i = 0, j = 0;
int k = l;
/*将左右两数组有序合并*/
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
k++;
}

/* 将L[]剩余元素拷贝到 数组 */
while (i < n1) {
a[k] = L[i];
i++;
k++;
}

/* 将R[]剩余元素拷贝到 数组*/
while (j < n2) {
a[k] = R[j];
j++;
k++;
}
}

5. 快速排序

算法描述:它选择一个元素作为枢轴(pivot),并围绕拾取的枢轴分割给定的数组。

详细分解:

  1. 从数组挑出一个元素,枢轴(pivot),可以始终选择第一个(最后一个|随机|中位数)元素作为枢轴。

    1. 分区,将比枢轴值小的摆放在枢轴前面,所有元素比枢轴值大的摆在枢轴的后面(相同的数可以到任一边)
  2. 递归地(recursive)把小于枢轴值元素的子数列和大于枢轴值元素的子数列排序。

图解:

sort_quick

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
quickSort(int a[], int l, int r) {

if (l < r) {

int partitionIndex = partition(a, l, r);



// 递归左右两边分区排序

quickSort(a, l, partitionIndex - 1);

quickSort(a, partitionIndex + 1, r);

}

}


int partition(int a[], int l, int r) {
int pivot = a[r];
int i = (l - 1); // 比枢轴元素小的游标
for (int j = l; j < r; j++) {
if (a[j] <= pivot) {
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

// 将枢轴元素插入中间
int temp = a[i + 1];
a[i + 1] = a[r];
a[r] = temp;

// 返回当前枢轴元素下标
return i + 1;
}