排序
承灿 2023/10/18
- 稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
- 不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
- 时间复杂度： 描述一个算法执行所耗费的时间；
- 空间复杂度：描述一个算法执行所需内存的大小；
- n：数据规模；
- k：“桶”的个数；
- In-place：占用常数内存，不占用额外内存；
- Out-place：占用额外内存。
该十种排序算法可分为如下所示的两大类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlog \log logn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
# 1、冒泡排序（Bubble Sort）
算法步驟
- 比较相邻的元素，如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
- 针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；
- 重复步骤1~3，直到排序完成。
代码实现
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
boolean flag = true;
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
}
}
# 2、选择排序（Selection Sort）
算法步驟
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
- 重复第2步，直到所有元素均排序完毕。
代码实现
public class SelectionSort {
public static void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int minVal = i;
for (int j = i + 1; j < len; j++) {
if (arr[minVal] > arr[j]) {
minVal = j;
}
}
if (minVal != i) {
int tmp = arr[i];
arr[i] = arr[minVal];
arr[minVal] = tmp;
}
}
}
}
# 3、插入排序（Insertion Sort）
算法步驟
- 首先从第一个元素开始，该元素被认为是有序的；
- 取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
- 如果该已排好序的元素大于新元素，则将该元素移到下一位置；
- 重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
代码实现
public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int val = arr[i], j = i;
while (j > 0 && val < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = val;
}
}
}
# 4、希尔排序（Shell Sort）
算法步驟
- 选择一个增量序列{t1, t2, …, tk}；
- 按增量序列个数k，对序列进行k趟排序；
- 每趟排序，根据对应的增量t，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
其中，增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, …, 1}，称为增量序列。一般的增量序列都选择以上说明的这个，但不一定是最优的。 
代码实现
public class ShellSort {
public static void shellSort(int[] arr) {
int len = arr.length, tmp, j;
for (int gap = len / 2; gap >= 1; gap = gap / 2) {
for (int i = gap; i < len; i++) {
tmp = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
}
}
}
# 5、归并排序（Merge Sort）
算法步驟
- 如果待排序列只有一个元素，则直接返回，否则将长度为n的待排序列分成两个长度为n/2的子序列，递归进行调用进行分割知道每个子序列中只有一个元素；
- 此时的每个子序列被认为是有序的，然后递归调用的返回子序列进行两两合并；
- 合并过程中完成排序操作，具体操作为设定两个指针，分别指向两个已经排序子序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并返回的数组，并移动指针到下一位置；
- 重复步骤3~4直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾，最终得到的新序列就是有序序列。
代码实现
import java.util.Arrays;
public class MergeSort {
public static int[] mergeSort(int[] arr) {
int len = arr.length;
if (len < 2) {
return arr;
}
int mIdx = len / 2;
return merge(mergeSort(Arrays.copyOfRange(arr, 0, mIdx)), mergeSort(Arrays.copyOfRange(arr, mIdx, len)));
}
private static int[] merge(int[] arrLeft, int[] arrRight) {
int leftLen = arrLeft.length, rightLen = arrRight.length, leftIdx = 0, rightIdx = 0, idx = 0;
int[] result = new int[leftLen + rightLen];
while (leftIdx < leftLen && rightIdx < rightLen) {
if (arrLeft[leftIdx] < arrRight[rightIdx]) {
result[idx++] = arrLeft[leftIdx++];
} else {
result[idx++] = arrRight[rightIdx++];
}
}
while (leftIdx < leftLen) {
result[idx++] = arrLeft[leftIdx++];
}
while (rightIdx < rightLen) {
result[idx++] = arrRight[rightIdx++];
}
return result;
}
}
# 6、快速排序（Quick Sort）
算法步驟
- 从序列中随机挑出一个元素，做为基准（pivot，这里选择序列的最左边元素作为基准）；
- 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置。这个操作称为分区（partition）；
- 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行上述操作即可。
代码实现
package com.example.leetcode.sort;
/**
* @author: lichengcan
* @date: 2023-11-14 15:29
* @description
**/
public class QuickSort {
public static void main(String[] args) {
int[] array = {64, 12, 34, 25, 12, 22, 11, 90, 111, 2, 7, 1, 88, 33};
int[] array2 = {64, 12, 34, 25, 12, 22, 11, 90, 111, 2, 7, 1, 88, 33};
System.out.println("原始数组：");
for (int anInt : array) {
System.out.print(" " + anInt);
}
int[] ints = quickSort(array, 0, array.length - 1);
System.out.println("\n排序后的数组：");
for (int anInt : ints) {
System.out.print(" " + anInt);
}
}
public static int[] quickSort(int array[], int start, int end) {
//循环条件
if (start < end) {
int partion = partion(array, start, end);
//继续给base位置左侧的元素排序
quickSort(array, start, partion - 1);
//继续给base位置右侧的元素排序
quickSort(array, partion + 1, end);
}
return array;
}
public static int partion(int array[], int left, int right) {
int base = array[left];//基准元素
//继续循环
while (left < right) {
//从右往左走，因为替换的时候是和左侧的base进行交换，左侧应该放小的，所以需要找到小的数时才进行替换
//所以下面需要用一个while
//从右--》左，找到大的就--，找到小的就替换base位置
//下面array[right] >= base一定要加上‘=’号，不然在相等的时候指针就不动了，会进入无线循环
while (left < right && array[right] >= base) {
right--;
}
//小的，替换base位置的值
//这时base位置变成了 array[right]
array[left] = array[right];
//从左--》右，找到小的就--
while (left < right && array[left] <= base) {
left++;
}
//找到大的就替换base位置的值
//这时base位置变成array[left]
array[right] = array[left];
}
//当left = right 代表当前一小轮结束了
//用base值替换指针位置的值
array[left] = base;
return left;
}
}
# 7、堆排序（Heap Sort）
算法步驟
- 将待排序列(R0, R1, ……, Rn)构建成最大堆（最小堆）；
- 将堆顶元素R[0]与最后一个元素R[n]进行交换，此时得到新的无序区(R0, R1, ……, Rn-1)和新的有序区(Rn),且满足R[0, 1, ……, n-1]<=R[n]（>=R[n]）；
- 由于调整后的新堆可能违反堆的性质，因此需要对当前无序区(R0, R1, ……, Rn-1)进行调整；
- 重复步骤2~3直到有序区的元素个数为n。
代码实现
public class HeapSort {
private static int heapLen;
public static void heapSort(int[] arr) {
heapLen = arr.length;
for (int i = heapLen - 1; i >= 0; i--) {
heapify(arr, i);
}
for (int i = heapLen - 1; i > 0; i--) {
swap(arr, 0, heapLen - 1);
heapLen--;
heapify(arr, 0);
}
}
private static void heapify(int[] arr, int idx) {
int left = idx * 2 + 1, right = idx * 2 + 2, largest = idx;
if (left < heapLen && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapLen && arr[right] > arr[largest]) {
largest = right;
}
if (largest != idx) {
swap(arr, largest, idx);
heapify(arr, largest);
}
}
private static void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
# 8、计数排序（Counting Sort）
算法步驟
- 找出数组中的最大值maxVal和最小值minVal；
- 创建一个计数数组countArr，其长度是maxVal-minVal+1，元素默认值都为0；
- 遍历原数组arr中的元素arr[i]，以arr[i]-minVal作为countArr数组的索引，以arr[i]的值在arr中元素出现次数作为countArr[a[i]-min]的值；
- 遍历countArr数组，只要该数组的某一下标的值不为0则循环将下标值+minVal输出返回到原数组即可。
代码实现
public class CountingSort {
public static void countingSort(int[] arr) {
int len = arr.length;
if (len < 2) return;
int minVal = arr[0], maxVal = arr[0];
for (int i = 1; i < len; i++) {
if (arr[i] < minVal) {
minVal = arr[i];
} else if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
int[] countArr = new int[maxVal - minVal + 1];
for (int val : arr) {
countArr[val - minVal]++;
}
for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) {
while (countArr[countIdx]-- > 0) {
arr[arrIdx++] = minVal + countIdx;
}
}
}
}
# 9、桶排序（Bucket Sort）
算法步驟
- 设置一个bucketSize（该数值的选择对性能至关重要，性能最好时每个桶都均匀放置所有数值，反之最差），表示每个桶最多能放置多少个数值；
- 遍历输入数据，并且把数据依次放到到对应的桶里去；
- 对每个非空的桶进行排序，可以使用其它排序方法（这里递归使用桶排序）；
- 从非空桶里把排好序的数据拼接起来即可。
代码实现
import java.util.ArrayList;
import java.util.List;
public class BucketSort {
private static List<Integer> bucketSort(List<Integer> arr, int bucketSize) {
int len = arr.size();
if (len < 2 || bucketSize == 0) {
return arr;
}
int minVal = arr.get(0), maxVal = arr.get(0);
for (int i = 1; i < len; i++) {
if (arr.get(i) < minVal) {
minVal = arr.get(i);
} else if (arr.get(i) > maxVal) {
maxVal = arr.get(i);
}
}
int bucketNum = (maxVal - minVal) / bucketSize + 1;
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>());
}
for (int val : arr) {
int idx = (val - minVal) / bucketSize;
bucket.get(idx).add(val);
}
for (int i = 0; i < bucketNum; i++) {
if (bucket.get(i).size() > 1) {
bucket.set(i, bucketSort(bucket.get(i), bucketSize / 2));
}
}
List<Integer> result = new ArrayList<>();
for (List<Integer> val : bucket) {
result.addAll(val);
}
return result;
}
}
# 10、基数排序（Radix Sort）
算法步骤
- 取得数组中的最大数，并取得位数，即为迭代次数n（例如：数组中最大数为123，则 n=3）；
- arr为原始数组，从最低位（或最高位）开始根据每位的数字组成radix数组（radix数组是个二维数组，其中一维长度为10），例如123在第一轮时存放在下标为3的radix数组中；
- 将radix数组中的数据从0下标开始依次赋值给原数组；
- 重复2~3步骤n次即可。
代码实现
import java.util.ArrayList;
import java.util.List;
//基数排序
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr.length < 2) return;
int maxVal = arr[0];//求出最大值
for (int a : arr) {
if (maxVal < a) {
maxVal = a;
}
}
int n = 1;
while (maxVal / 10 != 0) {
//求出最大值位数
maxVal /= 10;
n++;
}
for (int i = 0; i < n; i++) {
List<List<Integer>> radix = new ArrayList<>();
for (int j = 0; j < 10; j++) {
radix.add(new ArrayList<>());
}
int index;
for (int a : arr) {
index = (a / (int) Math.pow(10, i)) % 10;
radix.get(index).add(a);
}
index = 0;
for (List<Integer> list : radix) {
for (int a : list) {
arr[index++] = a;
}
}
}
}
}
# 11、总结
数据量规模较小，考虑插入或选择。当元素分布有序时插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用选择，效率略高于插入； 数据量规模中等，使用希尔排序； 数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）； 一般来说不使用冒泡。