常见排序算法
分析排序算法
- 执行效率
- 最好, 最坏, 平均时间复杂度
- 当时间复杂度相同时, 要考虑系数, 常量, 低阶
- 比较次数或交换次数
- 内存消耗, 原地排序(特指空间复杂度为O(1)的算法)
- 稳定性, 如果待排序的序列中存在值相等的元素, 经过排序之后, 相等元素之间原有的先后顺序不变
- 举例, 要给订单按照金额从小到大排序, 对于金额相同, 按照下单时间从早到晚排序; 若先按照金额对订单进行排序, 再遍历排序之后的订单, 对于金额相同的小区间再按照下单时间排序, 实现会教复杂; 借助稳定排序算法, 可先按下单时间给订单排序, 再用稳定排序算法对订单金额重新排序即可
冒泡排序
- 原理: 从左到右遍历数组, 每次遍历中依次比较相邻元素, 若不满足大小关系则互换位置, 事实上每次冒泡都会找到当下最大/小的元素移至右侧合适的位置
Java
publicclassBubbleSort {
// 测试冒泡排序的方法
publicstaticvoidmain(String[] args) {
int[] arrayToSort = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前：");
System.out.println(Arrays.toString(arrayToSort));
bubbleSort(arrayToSort); // 调用冒泡排序
System.out.println("排序后：");
System.out.println(Arrays.toString(arrayToSort));
}
privatestaticvoidbubbleSort(int[] array) {
intn = array.length;
booleanswapped = false;
for(inti = 0; i < n - 1; i++) {
for(intj = 0; j < n - 1 - i; j++) {
if(array[j] > array[j + 1]) {
inttemp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
if(!swapped) {
break;
}
}
}
}
- 优化: 当某次冒泡操作已经没有数据交换时, 说明已经达到完全有序, 不用再继续执行后续的冒泡操作
- 分析
空间复杂度O(1)/原地排序算法
稳定排序
时间复杂度, 平均时间复杂度为
$$ O(n^2) $$
插入排序
- 原理: 将数组分为已排序区和未排序区, 初始时只有数组的第一个元素是已排序区; 取未排序区间中的元素, 在已排序区中找到合适的位置插入, 重复这个过程, 直到未排序区中元素为空
Java
publicclassInsertionSort {
publicstaticvoidmain(String[] args) {
int[] arrayToSort = {12, 11, 13, 5, 6};
System.out.println("排序前：");
System.out.println(Arrays.toString(arrayToSort));
insertionSort(arrayToSort); // 调用插入排序
System.out.println("排序后：");
System.out.println(Arrays.toString(arrayToSort));
}
privatestaticvoidinsertionSort(int[] arr) {
intn = arr.length;
for(inti = 1; i < n; i++) {
// i是未排序区待排序的第一个元素的下标, key是从未排序区取出的第一个待排序的元素
intkey = arr[i];
// j是有序区的下标, 从末尾开始对比
intj = i - 1;
for(; j >= 0; j--) {
if(arr[j] > key) {
// j位置的元素比key大, 则往右移
arr[j + 1] = arr[j];
} else{
break;
}
}
// 直至j位置的元素比key小, 那么key就放在j+1的位置
arr[j + 1] = key;
}
}
}
- 分析
原地排序
稳定排序
平均时间复杂度** $$ O(n^2) $$
**
选择排序
- 原理: 也是将数组分为已排序区和未排序区, 每次会从未排序区找到最小的元素, 将其放到已排序区的末尾
Java
publicclassSelectionSort {
publicstaticvoidmain(String[] args) {
int[] arrayToSort = {64, 25, 12, 22, 11};
System.out.println("排序前：");
System.out.println(Arrays.toString(arrayToSort));
selectionSort(arrayToSort); // 调用选择排序
System.out.println("排序后：");
System.out.println(Arrays.toString(arrayToSort));
}
privatestaticvoidselectionSort(int[] arr) {
intn = arr.length;
for(inti = 0; i < n - 1; i++) {
// 假设当前元素是最小的
intminIndex = i;
for(intj = i + 1; j < n; j++) {
if(arr[j] < arr[minIndex]) {
// 从未排序部分寻找最小元素
minIndex = j;
}
}
// 如果找到了新的最小值, 则交换位置
if(minIndex != i) {
inttemp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
- 分析
原地排序
不稳定, 比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了
最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 ** $$ O(n^2) $$
**
归并排序
- 原理: 把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了
- 使用递归来实现归并排序, 写递归技巧, 得到递推公式+找到终止条件
Java
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解
q=(p+r)/2Java
publicclassMergeSort {
// 主方法用于测试
publicstaticvoidmain(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Original array:");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length - 1);
System.out.println("Sorted array:");
System.out.println(Arrays.toString(array));
}
// 归并排序方法
publicstaticvoidmergeSort(int[] array, intleft, intright) {
if(left < right) {
// 找到中间点
intmiddle = (left + right) / 2;
// 排序左半部分
mergeSort(array, left, middle);
// 排序右半部分
mergeSort(array, middle + 1, right);
// 合并两部分
merge(array, left, middle, right);
}
}
// 合并两个已经排序的子数组
publicstaticvoidmerge(int[] array, intleft, intmiddle, intright) {
// 创建临时数组来存储左右两部分
intn1 = middle - left + 1;
intn2 = right - middle;
// 创建临时数组
int[] L = newint[n1];
int[] R = newint[n2];
// 将数据复制到临时数组 L[] 和 R[]
for(inti = 0; i < n1; ++i)
L[i] = array[left + i];
for(intj = 0; j < n2; ++j)
R[j] = array[middle + 1 + j];
// 合并临时数组回原数组
inti = 0, j = 0;
intk = left;
while(i < n1 && j < n2) {
if(L[i] <= R[j]) {
array[k] = L[i];
i++;
} else{
array[k] = R[j];
j++;
}
k++;
}
// 检查是否还有剩余元素在 L[]
while(i < n1) {
array[k] = L[i];
i++;
k++;
}
// 检查是否还有剩余元素在 R[]
while(j < n2) {
array[k] = R[j];
j++;
k++;
}
}
}- 分析
稳定排序
最好, 最坏, 平均时间复杂度都是** $$ O(nlogn) $$
**
空间复杂度为O(n)
快速排序
- 原理:
- 如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
- 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
- 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
- 如果我们用递推公式来将上面的过程写出来的话，就是这样：
Java
递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
终止条件：
p >= r- 上面的递归是容易写的, 主要是为了实现原地排序(空间复杂度O(1)), 分区方法比较复杂, 思路类似于选择排序, 通过游标 i 把 A[p...r-1]分成两部分。A[p...i-1]的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i...r-1]是“未处理区间”。我们每次都从未处理的区间 A[i...r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。
Java
publicclassQuickSort {
// 主方法用于测试
publicstaticvoidmain(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Original array:");
System.out.println(Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println("Sorted array:");
System.out.println(Arrays.toString(array));
}
// 快速排序方法
publicstaticvoidquickSort(int[] array, intlow, inthigh) {
if(low < high) {
// pi 是分区索引，array[pi] 已经排好序
intpi = partition(array, low, high);
// 分别对左右子数组进行排序
quickSort(array, low, pi - 1); // 排序左半部分
quickSort(array, pi + 1, high); // 排序右半部分
}
}
// 分区方法，返回分区索引
privatestaticintpartition(int[] array, intlow, inthigh) {
intpivot = array[high]; // 选择最后一个元素作为基准
inti = low - 1; // 较小元素的索引
for(intj = low; j < high; j++) {
// 如果当前元素小于或等于pivot
if(array[j] <= pivot) {
i++;
// 交换array[i]和array[j]
inttemp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// 交换array[i+1]和array[high] (或pivot)
inttemp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
returni + 1;
}
}- 分析
非稳定排序
平均时间复杂度**
$$ O(nlogn) $$
, 最快时间复杂度
$$ O(n^2) $$
**
空间复杂度O(1)
- 快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？
- 归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题
- 归并是稳定的, 但非原地排序; 快拍不稳定, 但通过巧妙的原地分区函数, 可以实现原地排序, 解决了归并排序内存占用多的问题
总结
- 冒泡排序：通过重复地遍历列表，比较相邻元素并交换顺序错误的元素，每次遍历将最大（或最小）的元素“浮”到正确位置
- 插入排序：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
- 选择排序：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
- 快速排序：通过选定一个“基准”元素，将数组分为两部分，一部分比基准小，一部分比基准大，然后递归地对这两部分进行快速排序。
- 归并排序：将数组分成两半，分别对它们进行排序，然后将排序好的两半合并成一个有序数组。
- 桶排序，针对排序内存不足的情况，可先将序列分桶，每个桶内再排序，最后合并
- 计数排序，当排序的范围不大的时候，假设范围为K，可直接分K个桶，如给10万学生高考成绩排序，学生数量大，但高考成绩范围不大，可直接按高考满分成绩分桶
- 基数排序， 适用于元素可按位划分排序的情况，比如手机号排序，可先比较低位，再比较高位； 比如姓名排序，可按字符编码，先排低位， 再排高位