1. 七大排序算法简述
1.1 选择排序
算法思想：
- 进行n轮操作
- 在某一轮中，选择未排序的一个最小数组元素，与右侧未排序的第一个数组元素交换
- 交换完之后，相当于向右扩大已排序的数组范围。
- 重复2,3.直至所有数组元素已排序
稳定性：不稳定
假设在某一轮数组状态为：1,2,3,8,8,4。已排序的元素为1,2,3，此时会将第一个8与4交换，因此不稳定。
评价：我将其命名为SB排序，时间复杂度已经是O(n^2)，还不稳定，SB会使用?
代码如下：
public static void selectSort(int []arr){
for(int i=0;i<arr.length;i++){
int minIndex = i;
for(int j=i;j<arr.length;j++){
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
1.2 冒泡排序
算法思想：
- 进行n轮操作
- 在第一轮操作中，对数组元素逐个进行两两比较，将较大的交换到右侧
- 遍历完数组元素后，最大的元素会出现在数组最右侧，相当于减少了需要排序的数组范围
- 重复2,3操作，直至没有数组元素需要排序。
稳定性：稳定
代码：
public static void bubbleSort(int [] array){
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
1.3 插入排序
算法思想：
- 进行n轮操作，不断向右扩大已排序的元素个数
- 在某一轮中，对右侧未排序的第一个数组元素，不断向左交换，直至满足排序关系。
- 交换完之后，相当于向右扩大已排序的数组范围。
- 重复2,3.直至所有数组元素已排序
稳定性：稳定
代码如下：
public static void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){
for(int j=i-1;j>=0;j--) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
1.4 归并排序
算法思想：
- 进行log(n)轮操作，每轮将原数组划分为两个部分
- 首先不断划分不断划分，直至划分的部分只包含一个元素，也就是有序了。
- 这时函数开始返回，不断归并，归并过程就是合并两个有序数组，归并过程中需要申请额外的空间用于暂时保存合并后的结果。
- 直至归并到最顶层。
稳定性：稳定
评价：我觉得我这么讲，你如果第一次看，必然看不懂，但没关系，你可以查查其他资料。
代码如下：
public static void mergeSort(int []arr, int l, int r){
if(r-l<=1)return;
int mid = (l+(r-l)/2);
mergeSort(arr, l, mid);
mergeSort(arr, mid, r);
// merge
int []temp = new int[r-l];
int i1 = l;
int i2 = mid;
for(int i=0;i<temp.length;i++){
if(i1<mid&&i2<r){
if(arr[i1]<=arr[i2])temp[i] = arr[i1++];
else temp[i] = arr[i2++];
}else if(i1<mid){
temp[i] = arr[i1++];
}else{
temp[i] = arr[i2++];
}
}
// copy back
for(int i=0;i<temp.length;i++){
arr[l+i] = temp[i];
}
}
1.5 快速排序
算法思想：
- 进行log(n)操作
- 不断进行partition操作。partition指首先找一个基准数，然后将数组根据与基准数的大小关系分为<,=,>三个部分。接着对于>,<部分再进行partition。
- 直至所有元素都已经partition过了。
- 数组成为有序数组。
稳定性：不稳定。原因在于，partition过程中，存在两个不相邻的数的交换。设想一个数组的状态处于：1,2,8,8,4。并且基准数(pivot)为4。此时会将第一个8与4做交换，导致数组不再稳定。经过此轮partition，数组变为:1,2,4,8,8。但是两个8的相对位置关系已经改变。
注意：在选取pivot的index时，要随机选取一个位置。因为理想情况下我们希望每次partition正好将数组分为两半，这样可以快速的得到最终结果。而如果采取固定位置，可以人为构造出数组，使得时间复杂度为O(n^2). 比如固定选择最后一个位置，而数组本身就是有序的。
评价：相对于归并排序，快排的优势在于partition过程，不需要申请额外的空间
代码如下：
public static void quickSort(int []arr, int l, int r){
if(r-l<=1)return;
//use random index
int pivotIndex = (int)(Math.random()*(arr.length-1));
int pivot = arr[pivotIndex];
int [] partitionIndex = partition(arr, l, r, pivot);
quickSort(arr, l, partitionIndex[0]);
quickSort(arr, partitionIndex[1], r);
}
// Return an array that consists of
// the end of < partition and
// the start of > partition
public static int[] partition(int []arr, int l, int r, int pivot){
int lessEnd = l;
int gteStart = r;
int i = l;
while(i<gteStart){
if(arr[i]>pivot){
swap(arr, i, --gteStart );
}else if(arr[i] < pivot){
// remember to increment the i, to prevent lessEnd is bigger than i;
swap(arr, i++, lessEnd++);
}else{
i++;
}
}
return new int[]{lessEnd, gteStart};
}
public static void swap(int []arr, int i1,int i2){
int temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
1.6 堆排序
1.6.1 啥是堆
- 一种特殊的完全二叉树，分为大根堆，小根堆。大根堆中任意一个父节点的值>=其任意
子节点的值；而小根堆中任意一个父节点的值<=其任意子节点的值。
- 常用数组来表示堆（此处规则适用于所有完全二叉树）。
i) 父节点的索引为i，则子节点的索引为2i+1,2i+2.
ii) 子节点的索引为c，则父节点的索引 (c-1)/2
- 堆的两个重要操作
i) heapInsert. 向堆中添加一个元素 O(logn)
ii) heapify. 调整堆顶点元素的位置，恢复堆结构。O(logn)
1.6.2 利用堆结构实现堆排序
算法思想：
i) 将数组中元素逐个入大根堆。
ii) 大根堆推出首个元素
iii) 使剩余的大根堆有序
iv) 重复第二步和第三步
稳定性：不稳定。感觉这玩意儿涉及到了不相邻的元素比较了，对稳定性应该是无法保证的，不再详细证明
代码如下：
public static void heapSort(int arr[]){
// 堆化
for(int i=0;i<arr.length;i++){
heapInsert(arr, i);
}
// 开始排序. end indicates the end of heap(not include)
int end = arr.length;
while(end>1){
swap(arr, 0, end-1);
end--;
heapify(arr, end);
}
}
// [0, index) 位置已是大根堆结构。现将index位置添加至堆中。
public static void heapInsert(int arr[], int index){
int fatherIndex = (index-1)/2; // fatherIndex will never be negative
while(arr[fatherIndex]<arr[index]){
swap(arr, fatherIndex, index);
index = fatherIndex;
fatherIndex = (index-1)/2;
}
}
// [0,end)位置曾是大根堆结构，只有0位置数可能不满足，
// 现调整0位置的数，将[0, index)位置恢复为大根堆结构
public static void heapify(int arr[], int end){
int index = 0;
while(true){
int biggestIndex = index;
if(2*index+2<end){
int biggerChildIndex = arr[2*index+1]>arr[2*index+2]?2*index+1:2*index+2;
biggestIndex = arr[index]>=arr[biggerChildIndex]?index:biggerChildIndex;
}else if(2*index+1<end){
biggestIndex = arr[index]>=arr[2*index+1]?index:2*index+1;
}
if(biggestIndex == index){
break;
}
swap(arr, index , biggestIndex);
index = biggestIndex;
}
}
public static void swap(int arr[], int i1 ,int i2){
int temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
1.7 桶排序
桶排序：区别于之前的所有排序算法，此算法不基于数与数的比较。
而是依赖于数据的有限数据状况。
桶排序的思想：
- 不妨设数组中最大数有n位，那么需要n次入桶出桶的过程，每个桶是一个先进先出的队列。
- 每次入桶出桶的过程都需要有10个桶，对应了从0-9.
- 排序的过程，可以认为是首先根据个位数排序，然后十位数，直到最高位。。因为越高位
权重越大，所以要放在最后。之所以要先进先出是为了保证上一轮的排序结果没有遭到破坏。 - 有了这一基础思想，使用前缀和来对桶的概念进行优化，没有必要真的为每一个桶建立
一个队列。 - 根据前缀和数组，我们足以判断一个数应该放在排序后数组的哪个位置。
算法如下：
// 显式使用队列进行排序
public static void bucketSort(int []arr){
int maxWidth = 0;
// get max width among numbers
for(int num:arr){
maxWidth = Math.max(getWidth(num), maxWidth);
}
Queue<Integer> [] queues = new Queue[10];
// Put number in and out of buckets for "maxWidth" times.
int digitIndex = 0;// sort from index "0"
while(digitIndex<maxWidth){
for(int i=0;i<queues.length;i++){
queues[i] = new LinkedList<>();
}
for(int num:arr){
int digit = getDigitByIndex(num, digitIndex);
queues[digit].add(num);
}
// Rebuild array by the result.
int index = 0;
for(Queue<Integer> q: queues){
while(!q.isEmpty()){
arr[index++] = q.poll();
}
}
digitIndex++;
}
}
// 使用前缀和数组进行优化
public static void bucketSortWithPrefixSumArray(int []arr){
int maxWidth = 0;
// get max width among numbers
for(int num:arr){
maxWidth = Math.max(getWidth(num), maxWidth);
}
// Put number in and out of buckets for "maxWidth" times.
int digitIndex = 0;// sort from index "0"
while(digitIndex<maxWidth){
int [] prefixSum = new int[10] ;
for(int num:arr){
int digit = getDigitByIndex(num, digitIndex);
prefixSum[digit]++;
}
for(int i=1;i<prefixSum.length;i++){
prefixSum[i] = prefixSum[i]+prefixSum[i-1];
}
// Rebuild array by the result.
int temp[] =new int[arr.length];
for(int i= arr.length-1;i>=0;i--){
int digit = getDigitByIndex(arr[i], digitIndex);
temp[--prefixSum[digit]] = arr[i];
}
for(int i=0;i<temp.length;i++){
arr[i] = temp[i];
}
digitIndex++;
}
}
public static int getWidth(int num){
int width = 0;
while(num>0){
num/=10;
width++;
}
return width;
}
public static int getDigitByIndex(int num, int index){
while(index>0){
num/=10;
index--;
}
return num%10;
}
2. 各算法之间比较
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 补充 |
|---|---|---|---|---|
| 选择排序 | 严格O(n^2) | O(1) | N | |
| 冒泡排序 | 严格O(n^2) | O(1) | Y | |
| 插入排序 | O(n^2) | O(1) | Y | 时间复杂度与数据状况有关，最好O(n),最差O(n^2) |
| 归并排序 | O(nlogn) | O(n) | Y | 空间复杂度之所以为O(n), 是因为要暂时保存排序后的数组，此处O(n)是归并到最顶层，需要申请n个元素的空间。 |
| 快速排序 | O(nlogn) | O(logn) | N | 此处的快排指的随机取基准数下的时间和空间复杂度，空间复杂度之所以为log(n),是因为有这么多次递归，注意与归并区分。若取固定位置，可以人为构建数组，使得每次partiton都不平均，都全在一边，此时时间，空间复杂度会退化到O(n^2), O(n)。 |
| 堆排序 | O(nlogn) | O(1) | N | |
| 桶排序 | O(n) | O(n) | Y | |
总结
本文总结了常见的排序算法。除了桶排序之外，都属于基于比较的算法。基于比较的算法中时间复杂度为O(nlogn)包括：归并排序，快速排序和堆排序。
其中，归并排序和快速排序都使用到了递归，区别在于归并排序自下而上，而快速排序则是自上而下的；堆排序使用了堆（优先队列）这一数据结构，帮助完成了排序工作。实际测试中，快速排序的速度最快。
桶排序值得注意的点在于其使用了前缀和数组对入桶，出桶的操作进行了优化。