基础排序算法介绍
知识点:
- 排序算法稳定性的定义：简单的介绍就是排序前相等的数据先后顺序在排序后的先后顺序位置相同
- 基本交换算法
1
2
3
4
5
| private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
|
- 时间复杂度：执行算法所需要的计算工作量 $ O(1) $ 意味没有循环即只执行单条语句 $ O(n) $ 执行没有嵌套的循环 $ O(n^2) $ 双重嵌套循环
- 空间复杂度：算法在运行工程中临时占用存储空间的量度
算法 | 平均时间 | 最好 | 最差 | 空间复杂度 | 稳定性
- | :-: | :-: | :-: | :-: | :-: | :-: | -:
冒泡排序| $ O(n^2) $ | $ O(n) $ | $ O(n^2) $ | $ O(1) $ | 稳定
直接插入排序| $ O(n^2) $ | $ O(n) $ | $ O(n^2) $ | $ O(1) $ | 稳定
折半插入排序| $ O(nlogn) $ | $ O(nlogn) $ | $ O(n^2) $ | $ O(1) $ | 稳定
希尔排序| $ O(nlogn) $ - $ O(n^2) $ | $ O(n^1.3) $ | $ O(n^2) $ | $ O(1) $ | 不稳定
选择排序| $ O(n^2) $ | $ O(n^2) $ | $ O(n^2) $ | $ O(1) $ | 不稳定
快速排序| $ O(nlogn) $ | $ O(nlogn) $ | $ O(n^2) $ | $ O(nlogn) $ - $ O(n^2) $ | 不稳定
归并排序| $ O(nlogn) $ | $ O(nlogn) $ | $ O(nlogn) $ | $ O(n) $ | 稳定
堆排序| $ O(nlogn) $ | $ O(nlogn) $ | $ O(nlogn) $ | $ O(1) $ | 不稳定
排序算法
冒泡排序
在要排序的一组数中，对当前范围内还未排列好的数据由上而下进行比较，即每当相邻的数与要求的排序方式相反时将数据进行互换
改进版的写法就是利用标记法减少循环次数
基本写法
1
2
3
4
5
6
7
8
9
10
| private static void bubbleSort(int[] array) {
int size = array.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 1; j < size - i; j++) {
if (array[j - 1] > array[j]) {
swap(array, j, j - 1);
}
}
}
}
|
改进写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| private static void advancedBubbleSort(int[] array) {
int size = array.length;
int flag = 0;
for (int i = 0; i < size - 1; i++) {
flag = 0;
for (int j = 1; j < size - i; j++) {
if (array[j - 1] > array[j]) {
flag = 1;
swap(array, j, j - 1);
}
}
if (flag == 0)
break;
}
}
|
选择排序
再一次遍历过程中找到最小值放在排序数据中的首位，每次寻找剩余中最小的直到结束为止。
1
2
3
4
5
6
7
8
9
10
11
12
| private static void selectSort(int[] array) {
int size = array.length;
for (int i = 0; i < size; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
|
直接插入排序
按照顺序选定元素从后往前找，插入一个顺序数列中即可
1
2
3
4
5
6
7
8
9
10
| private static void InsertSort(int[] array) {
int size = array.length;
for (int i = 0; i < size; i++) {
int temp = array[i];
for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
|
折半插入排序
再往前寻找位置的过程中利用二分法寻找位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| private static void insertBinarySort(int[] array) {
int size = array.length;
for (int i = 1; i < size; i++) {
if (array[i] < array[i - 1]) {
int temp = array[i];
int low = 0, high = i - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (temp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int j = i; j > low; j--) {
array[j] = array[j - 1];
}
array[low] = temp;
}
}
}
|
希尔排序
先取d为间隔，将原始数组分为d个序列，将间隔的数组放在一个子序列利用插入排序法进行排序 然后缩小间隔d 重复上述操作，知道d为1时，则排序完成
1
2
3
4
5
6
7
8
9
10
11
12
13
| private static void shellSort(int[] array) {
int size = array.length;
for (int d = size / 2; d > 0; d /= 2) {
for (int i = 0; i < size; i += d) {
int temp = array[i];
int j = i;
for (; j >= d && temp < array[j - d]; j -= d) {
array[j] = array[j - d];
}
array[j] = temp;
}
}
}
|
基数排序
讲一组元素进行桶分配，按照每位数的大小进行排序
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
| private static void radixSort(int[] array) {
int size = array.length;
int max = array[0];
for (int i = 0; i < size; i++) {
if (array[i] > max)
max = array[i];
}
int time = 0;
while (max > 0) {
max /= 10;
time++;
}
int k = 0;
int m = 1;
int n = 1;
int[][] temp = new int[10][size];
int[] order = new int[10];
while (m <= time) {
for (int arr : array) {
int lsd = (arr / n) % 10;
temp[lsd][order[lsd]] = arr;
order[lsd]++;
}
for (int i = 0; i < 10; i++) {
if (order[i] != 0) {
for (int j = 0; j < order[i]; j++) {
array[k] = temp[i][j];
k++;
}
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
|
快速排序
通过排序将待排序记录分成两部分，其中一部分记录的关键字均比另一部分小，然后分别对这两部分进行排序，直到整个序列有序。快速排序在元素很少时，效率很低
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| private static void quickSort(int[] arr,int l,int r){
if(l>=r)
return;
int p=getMiddle(arr,l,r);
quickSort(arr,l,p-1);
quickSort(arr,p+1,r);
}
private static int getMiddle(int[] arr, int l, int r) {
int temp = arr[l];
int middle = l;
for (int i = middle + 1; i <= r; i++) {
if (arr[i] < temp) {
swap(arr, middle + 1, i);
middle++;
}
}
swap(arr, l, middle);
return middle;
}
|
归并排序
把待排序序列分成若干个有序子序列，然后再把子序列合并成一个有序序列。
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
| private static void mergeSort(int[] arr, int l, int r) {
int mid = (l + r) / 2;
if (l < r) {
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
while (i <= mid) {
temp[index++] = arr[i++];
}
while (j <= high) {
temp[index++] = arr[j++];
}
System.arraycopy(temp, 0, arr, low, temp.length);
}
|
堆排序
将数组构成大堆二叉树，即父节点比子节点大的二叉树，然后每次将根节点放在最后一位，循环遍历
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
|
private static void heapSort(int[] arr) {
buildMaxHeap(arr);
int length = arr.length;
for (int i = length - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeap(arr, i, 0);
}
}
private static void buildMaxHeap(int[] arr) {
int length = arr.length;
for (int i = length / 2 - 1; i >= 0; i--) {
maxHeap(arr, length, i);
}
}
private static void maxHeap(int[] arr, int length, int node) {
int left = 2 * node + 1;
int right = 2 * node + 2;
int maxIndex = node;
if (left < length && arr[left] > arr[maxIndex]) {
maxIndex = left;
}
if (right < length && arr[right] > arr[maxIndex]) {
maxIndex = right;
}
if (maxIndex != node) {
swap(arr, node, maxIndex);
maxHeap(arr, length, maxIndex);
}
}
|