您现在的位置是：首页 >学无止境 >排序算法学习网站首页学无止境
排序算法学习
简介排序算法学习
选择排序
首先，找到数组中最小的那个元素。
其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。
再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。
如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。
选择排序代码
public class Selection {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
int N = data.length;
for (int i = 0; i < N; i++) {
// 在data[i...N-1]中找到最小的值data[min], 将data[i]与data[min]交换
// 以第i个元素为基准值, 跟第data[i+1...N-1]的元素一一比较, 找到最小的
int min = i;
for (int j = i + 1; j < N; j++) {
// 找到一个更小的
if (data[min] > data[j]) {
min = j;
}
}
// 交换 i 和 min 的元素
SortUtils.swap(data, i, min);
}
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
排序流程
数组=[5 4 3 2 1 6 7 8 9 10 ]
i=0,min=4,[5 4 3 2 1 6 7 8 9 10 ],data[0]与data[4]交换
i=1,min=3,[1 4 3 2 5 6 7 8 9 10 ],data[1]与data[3]交换
i=2,min=2,[1 2 3 4 5 6 7 8 9 10 ],data[2]与data[2]交换
i=3,min=3,[1 2 3 4 5 6 7 8 9 10 ],data[3]与data[3]交换
i=4,min=4,[1 2 3 4 5 6 7 8 9 10 ],data[4]与data[4]交换
i=5,min=5,[1 2 3 4 5 6 7 8 9 10 ],data[5]与data[5]交换
i=6,min=6,[1 2 3 4 5 6 7 8 9 10 ],data[6]与data[6]交换
i=7,min=7,[1 2 3 4 5 6 7 8 9 10 ],data[7]与data[7]交换
i=8,min=8,[1 2 3 4 5 6 7 8 9 10 ],data[8]与data[8]交换
i=9,min=9,[1 2 3 4 5 6 7 8 9 10 ],data[9]与data[9]交换
[1 2 3 4 5 6 7 8 9 10 ]
可以发现，i=2时，整个数组已经有序了，但是还是要从data[i..N-1]中找到最小的元素与data[i]交换。
选择排序算法简单，但是有个缺点，无论数组是否有序，比较次数和交换次数是一样的。
对于长度为N的数组，选择排序需要比较[(N-1)*N]/2次，交换N次。证明如下。
| i | 比较次数 | 交换次数 | |
|---|---|---|---|
| 第1轮 | 0 | N-1 | 1 |
| 第2轮 | 1 | N-2 | 1 |
| … | … | ||
| 第(N-1)轮 | N-2 | 1 | 1 |
| 第N轮 | N-1 | 0 | 1 |
比较总次数为：[(0 + N-1) * N]/2 = [(N-1)*N]/2
交换总次数为：N
插入排序
通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。
在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。
这种算法叫做插入排序。
与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。
但是当索引到达数组的右端时，数组排序就完成了。
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。
例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。
插入排序代码
public class Insertion {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
int N = data.length;
// i 之前的元素已经是有序的的, 此时需要判断元素i是否需要插入到前面的某个位置
for (int i = 1; i < N; i++) {
int j = i;
// 一直向前比较, 如果遇到比前面小的则交换, 否则就退出比较
// 如果已经整体有序了就不需要往前比较了
while (j - 1 >= 0 && data[j] < data[j - 1]) {
// 交换 j 和 (j - 1)
SortUtils.swap(data, j, j - 1);
j--;
}
}
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
排序流程
数组=[5 4 3 2 1 6 7 8 9 10 ]
i = 1, [5 4 3 2 1 6 7 8 9 10 ]
data[1] 与 data[0]交换
i = 2, [4 5 3 2 1 6 7 8 9 10 ]
data[2] 与 data[1]交换
data[1] 与 data[0]交换
i = 3, [3 4 5 2 1 6 7 8 9 10 ]
data[3] 与 data[2]交换
data[2] 与 data[1]交换
data[1] 与 data[0]交换
i = 4, [2 3 4 5 1 6 7 8 9 10 ]
data[4] 与 data[3]交换
data[3] 与 data[2]交换
data[2] 与 data[1]交换
data[1] 与 data[0]交换
i = 5, [1 2 3 4 5 6 7 8 9 10 ]
i = 6, [1 2 3 4 5 6 7 8 9 10 ]
i = 7, [1 2 3 4 5 6 7 8 9 10 ]
i = 8, [1 2 3 4 5 6 7 8 9 10 ]
i = 9, [1 2 3 4 5 6 7 8 9 10 ]
[1 2 3 4 5 6 7 8 9 10 ]
对于随机排列的长度为N且不重复的数组，最坏情况下需要[N*(N-1)]/2次比较和[N*(N-1)]/2次交换，最好情况下需要N-1次比较和0次交换。
证明如下
| i | 最好比较次数 | 最好交换次数 | 最差比较次数 | 最差交换次数 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 2 | 2 |
| … | … | … | … | … |
| N-2 | 1 | 0 | N-2 | N-2 |
| N-1 | 1 | 0 | N-1 | N-1 |
最好情况：比较次数=N-1，交换次数=0。
最坏情况：比较次数=[(1+N-1)*(N-1)]/2 = [N*(N-1)]/2，交换次数=[(1+N-1)*(N-1)]/2 = [N*(N-1)]/2。
插入排序适用场景：
①大多数元素已经有序。如果数组中大部分元素已经有序，排序过程中就不需要频繁交换和比较。
②元素数量较少。插入排序的工作量和N的平方成正比，如果N 比较小，那么排序的工作量就小很多。
希尔排序
插入排序对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。
例如，如果最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。
希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。
换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。
h的取值有多种方式，这里取初始值 h = N / 2，后面每次都对h减半，直至h=1。
假设数组长度为11，数组=[10,9,8,7,6,5,4,3,2,1,0]
第一轮 h = 5
数组 = [10,9,8,7,6,5,4,3,2,1,0]
h1 = [10,5,0]
h2 = [9,4]
h3 = [8,3]
h4 = [7,2]
h5 = [6,1]
5个数组使用插入排序后
h1 = [0,5,10]
h2 = [4,9]
h3 = [3,8]
h4 = [2,7]
h5 = [1,6]
数组 = [0, 4, 3, 2, 1, 5, 9, 8, 7, 6, 10]
第二轮 h = 5 / 2 = 2
数组 = [0, 4, 3, 2, 1, 5, 9, 8, 7, 6, 10]
h1 = [0,3,1,9,7,10]
h2 = [4,2,5,8,6]
2个数组使用插入排序后
h1 = [0,1,3,7,9,10]
h2 = [2,4,5,6,8]
数组 = [0,2,1,4,3,5,7,6,9,8,10]
第三轮 h = 2 / 2 = 1
数组 = [0,2,1,4,3,5,7,6,9,8,10]
h1 = [0,2,1,4,3,5,7,6,9,8,10]
对h1数组使用插入排序后
h1 = [0 1 2 3 4 5 6 7 8 9 10 ]
数组 = [0 1 2 3 4 5 6 7 8 9 10 ]
希尔排序代码
public class Shell {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
int N = data.length;
int h = N;
while (true) {
h = h / 2;
if (h == 0) {
break;
}
for (int x = 0; x < h; x++) {
for (int i = x + h; i < N;) {
int j = i;
while (j - h >= 0 && data[j - h] > data[j]) {
// 交换j和(j-h)
SortUtils.swap(data, j, j - h);
j-=h;
}
i+=h;
}
}
}
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
归并排序
将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
你将会看到，归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；
它的主要缺点则是它所需的额外空间和N成正比。
归并排序分为分组和归并两个部分。
分组：假设数组有n个元素，将数组进行折半分组。
第一层：分为2个组，每组n/2个元素。
第二层：分为4个组，每组n/4个元素。
第三层：分为8组，每组n/8个元素。
一直分到每组只剩1个元素为止。
归并：最底层每组只剩下1个元素了，小组之间进行合并。从最后一层不断向前合并，每次都是两个有序数组进行合并。
排序流程，假设数组元素如下所示
| 数组 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
先分组
然后合并
归并排序代码
public class Merge {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
mergeSort(data, 0, data.length - 1);
}
public static void mergeSort(int[] data, int l, int r) {
if (l == r) {
return;
}
// 防止溢出 相当于 mid = (l + r) / 2
int mid = l + (r - l) / 2;
mergeSort(data, l, mid);
mergeSort(data, mid + 1, r);
merge(data, l, mid, r);
}
// 合并两个有序的数组
private static void merge(int[] data, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int p1 = l, p2 = mid + 1;
int index = 0;
while (p1 <= mid && p2 <= r) {
help[index++] = data[p1] < data[p2] ? data[p1++] : data[p2++];
}
while (p1 <= mid) {
help[index++] = data[p1++];
}
while (p2 <= r) {
help[index++] = data[p2++];
}
for (int i = 0; i < help.length; i++) {
data[l + i] = help[i];
}
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
堆排序
堆是一种特殊的树，它满足需要满足两个条件：
（1）堆是一种完全二叉树，也就是除了最后一层，其他层的节点个数都是满的，最后一个节点都靠左排列。
（2）堆中每一个节点的值都必须大于等于（或小于等于）其左右子节点的值。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大根堆。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小根堆。
对于数组中的某个下标元素i，i从0开始，其左孩子的下标为2*i+1，其左孩子的下标为2*i+2。
堆排序算法流程：
1.将数组构造成大根堆或者小根堆。
2.将数组的第一个元素与最后一个元素交换后将数组长度减1，然后从树的根节点开始往下沉，构造小根堆或者大根堆。不断重复这个过程，最终数组变得有序。
堆排序流程
排序流程，假设数组元素如下所示
| 数组 | 1 | 3 | 5 | 7 | 9 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| 下标i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
根据数组得到的二叉树
第一步：构建大根堆。
构造出来的大根堆如下所示
第二步：将第一个元素与最后一个元素交换，数组长度减1，从第一个元素往下比较，重新构建大根堆。不断重复第二步。
堆排序代码
public class Heap {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
int N = data.length;
// 将数组构建成大根堆
for (int i = 0; i < N; i++) {
swim(data, i);
}
// 此时已经数组的首个元素已经是最大值了
// size用来记录当前数组中还有多少个元素没有确定好顺序
int size = N;
// 将数组的第一个元素与最后一个元素交换
SortUtils.swap(data, 0, --size);
// 交换后数组的最后一个元素就是最大值, 此时已经确定了一个元素, 因此size减1
// 上面交换元素后, 此时就可能不是大根堆了, 所以需要从第一个元素开始比较, 使得数组是一个大根堆
while (size > 0) {
// 调整堆
sink(data, 0, size);
// 将数组的第一个元素与最后一个元素交换
SortUtils.swap(data, 0, --size);
}
}
/**
* 从index位置向下调整
*/
public static void sink(int[] data, int index, int size) {
// 找到左孩子的下标
int left = 2*index + 1;
while (left < size) {
// 找到左孩子和右孩子中最大的下标
int big = left + 1 < size && data[left + 1] > data[left] ? (left + 1) : left;
// 比较 data[index] 和 data[big]
if (data[big] > data[index]) {
// 此时子孩子比自己大, 需要与其交换
SortUtils.swap(data, index, big);
index = big;
left = 2*index + 1;
} else {
break;
}
}
}
/**
* 从index位置向上调整
*/
public static void swim(int[] data, int index) {
// (index - 1) / 2 为父元素的下标
while (data[index] > data[(index - 1) / 2]) {
// 如果比父元素大, 则与父元素交换位置
SortUtils.swap(data, index, (index - 1) / 2);
// 去到父元素的位置
index = (index - 1) / 2;
}
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
快速排序
快速排序的基本思想是:通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
一趟快速排序的过程称为一次划分，具体做法是:
假设两个位置指示变量i和j，它们的初值分别指向序列的第一个记录和最后一个记录。
基准记录(通常是第一个记录)的关键字为pivot，则首先从j所指位置起向前搜索，找到第一个关键字小于pivot的记录时将该记录向前移到i指示的位置，
然后从i所指位置起向后搜索，找到第一个关键字大于pivot的记录时将该记录向后移到j所指位置所指位置，重复该过程直至i与j相等为止。
快速排序代码
public class Quick {
public static void sort(int[] data) {
if (data == null || data.length < 2) {
return;
}
quickSort1(data, 0, data.length - 1);
// quickSort2 优化后的快速排序
// quickSort2(data, 0, data.length - 1);
}
private static void quickSort1(int[] data, int low, int high) {
if (low >= high) {
return;
}
int p = partition1(data, low, high);
System.out.println(Arrays.toString(data) + " p = " + p);
quickSort1(data, low, p - 1);
quickSort1(data, p + 1, high);
}
/**
* 以首个元素为基准值, 将小于pivot的元素移动到左边, 将大于等于pivot的元素移动到右边
*/
private static int partition1(int[] data, int low, int high) {
int i = low, j = high;
int pivot = data[low];
while (i < j) {
// 从后寻找比pivot小的
while (i < j && data[j] >= pivot) {
j--;
}
// 此时j就是比pivot小的元素, 把小的移动到前面
data[i] = data[j];
// 从前寻找比pivot大的
while (i < j && data[i] < pivot) {
i++;
}
// 此时的i就是比pivot大的, 把小的移动到后面
data[j] = data[i];
}
//
data[i] = pivot;
return i;
}
private static void quickSort2(int[] data, int low, int high) {
if (low >= high) {
return;
}
int[] p = partition2(data, low, high);
quickSort2(data, low, p[0] - 1);
quickSort2(data, p[1] + 1, high);
}
private static int[] partition2(int[] data, int low, int high) {
int less = low - 1;
int more = high;
while (low < more) {
if (data[low] < data[high]) {
SortUtils.swap(data, ++less, low++);
} else if (data[low] > data[high]) {
SortUtils.swap(data, --more, low);
} else {
low++;
}
}
SortUtils.swap(data, more, high);
return new int[] { less + 1, more };
}
public static void main(String[] args) {
// 测试算法是否正确
int testTime = 500000;
int maxSize = 200;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// 随机生成一个数组
int[] arr1 = SortUtils.generateRandomArray(maxSize, maxValue);
int[] arr2 = SortUtils.copyArray(arr1);
// 使用自己写的方法排序
sort(arr1);
// 使用Java提供的排序
Arrays.sort(arr2);
// 判断两个数组是否一样
if (!SortUtils.isEqual(arr1, arr2)) {
succeed = false;
SortUtils.printArray(arr1);
SortUtils.printArray(arr2);
break;
}
}
System.out.println(succeed ? "通过!" : "不通过");
}
}
SortUtils代码
public class SortUtils {
/**
* 生成一个随机数组
* @param maxSize 数组最大长度
* @param maxValue 最大值
*/
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
/**
* 复制数组
*/
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
/**
* 判断两个数组是否相等
*/
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
System.out.println(Arrays.toString(arr));
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] array = generateRandomArray(100, 100);
System.out.println(Arrays.toString(array));
}
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)