排序算法整理
Algorithms 4th的排序算法整理
这周把algorithm 4th这本书上的排序算法简单整理了一下，留做以后备用，也顺便水一篇博文。
[TOC]
缝合奇美拉文章notion版点这里
排序算法总体比较
稳定性
如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。
- 稳定的排序算法：插入排序、归并排序
- 不稳定的排序算法：选择排序、希尔排序、快速排序和堆排序
一般只有在稳定性是必要的情况下，稳定的排序算法才有优势。
各种排序算法的性能特点
快速排序是最快的通用排序算法。
插入排序(Insertion sort)
（1）设待排序数组a[n]，默认a[0]是一个有序序列
（2）循环n-1次，每次将为排序序列插入到前面的已排序序列当中，将已排序序列区间长度加1，未排序区间长度减一
（3）重复（2）直到未排序区间长度为0
插入排序每次将正在遍历的元素插入到其他已经有序的元素中的适当位置。与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定。为了给更小的元素腾出空间，它们可能会向右移动。当索引到达数组的右端时，数组排序就完成了。
java代码：
// 插入排序
public void insertSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
// 假设第一个数位置是正确的
for (int i = 1; i < nums.length; i++) {
int j = i;
int target = nums[j];
// 后移
while (j > 0 && nums[j - 1] > target) {
nums[j] = nums[j - 1];
j--;
}
// 插入
nums[j] = target;
}
}
python代码：
def InsertSort(ls):
n=len(ls)
if n<=1:
return ls
for i in range(1,n):
j=i
target=ls[i] #每次循环的一个待插入的数
while j>0 and target<ls[j-1]: #比较、后移，给target腾位置
ls[j]=ls[j-1]
j=j-1
ls[j]=target #把target插到空位
return ls
每轮操作O(n)次，共O(n)轮，时间复杂度O(n^2)。
额外空间开销出在数据移位时那一个过渡空间，空间复杂度O(1)。
对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要 ~N^2/4 次比较以及 ~N^2/4 次交换。最坏情况下需要 ~N^2/2 次比较和 ~N^2/2 次交换，最好情况下需要 N-1 次比较和 0 次交换。
选择排序(Selection sort)
通过n-1次关键字比较，从n-i+1个记录中选择关键字最小的记录，并和第i个记录交换。
选择排序是经过一次一次在无序区间中找到最值，放到无序区间的前一个位置，基本步骤：
（1）设待排序的记录存放在数组r[n]中，第一趟从r[1]开始，通过n-1次比较，从n个记录中选取最小的记录，记为r[k]，交换r[1]和r[k]
（2）第二趟从r[2]开始，通过n-2次比较，从n-1个记录中选出关键字最小的记录，记为r[k]，交换r[2]和r[k]
（3）以此类推，第i趟从r[i]开始，通过n-i次比较，从n-i+1个记录中选取最小关键字记录，记为r[k]，交换 r[i]和r[k]
（4）经过n-1趟，排序完成
其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。
动态图如下：
java代码：
// 选择排序
public void selectSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int minIndex;
// 只需要循环 n-1 次
for (int i = 0; i < nums.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
//交换两个值
if (minIndex != i) {
swap(nums, i, minIndex);
}
}
}
python代码：
def SelectSort(ls):
n=len(ls)
if n<=1:
return ls
for i in range(0,n-1):
minIndex=i
for j in range(i+1,n): #比较一遍，记录索引不交换
if ls[j]<ls[minIndex]:
minIndex=j
if minIndex!=i: #按索引交换
(ls[minIndex],ls[i])=(ls[i],ls[minIndex])
return ls
每轮操作O(n)次，共O(n)轮，时间复杂度O(n^2)。
额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
选择排序的特点：
- 运行时间和输入无关：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长；
- 数据移动是最少的：每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。其他算法大多都是线性对数或是平方级别。
冒泡排序(Bubble sort)
很少用，通过与相邻元素的比较和交换来把小的数交换到最前面，或者把大的数交换到最后面。
有一个数组a[10]，用变量i表示它的下标(i从0开始）
（1） 比较两个相邻元素a[i]和a[i+1]，如果a[i]>a[i+1]，就交换这两个数的位置；
（2）重复执行第一步，直到比较到最后一对的时候（例：首次是a[8]和a[9]，此时，a[9]的值为该数组的最大值，这个值属于有序数列）；
（3）对所有元素（除了有序数列里的元素），重复执行第一步和第二步，每执行完一次，都会找到当前比较的数里最大的那个（有序数列就会增加一个）；
（4）随着参与比较的元素越来越少，最终没有任何一对元素需要比较的时候，排序完成。
java代码：
// 冒泡排序
public void bubbleSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
// 只需要循环 n-1 次
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
python代码
def BubbleSort(ls):
n=len(ls)
if n<=1:
return ls
for i in range (0,n):
for j in range(0,n-i-1):
if ls[j]>ls[j+1]:
(ls[j],ls[j+1])=(ls[j+1],ls[j])
return ls
每轮操作O(n)次，共O(n)轮，时间复杂度O(n^2)。
额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。
希尔排序(Shell sort)
希尔排序是一种基于插入排序的快速的排序算法，为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
思想：使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。换句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起的一个数组。
官方java代码：
public static void sort(Comparable[] a) {
// 将 a[] 按升序排列
int N = a.length;
int h = 1;
while(h < N / 3)
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
while(h >= 1) {
// 将数组变为 h 有序
for(int i = h; i < N; i++) {
// 将 a[i] 插入到 a[i-h]，a[i-2*h]，a[i-3*h]... 之中
for(int j = i; j >= h && less(a[j], a[j -h]); j -= h)
exch(a, j, j-h);
}
h /= 3;
}
}
归并排序(Merge sort)
归并：将两个有序的数组归并成一个更大的有序数组。
归并排序能保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；但主要缺点是所需的额外空间和 N 成正比。
归并算法是算法设计中分治思想的典型应用。
（1）将当前序列一分为二，求出分裂点mid=(l+r)/2
（2）对子序列r[l]-r[mid]递归，进行归并排序，结果放在t[l,mid]中
（3）对子序列r[mid+1,r]递归，进行归并排序，结果放在t[mid+1,r]
（4）将两个有序的子序列t[l,mid]，t[mid+1,r]归并为一个有序的序列放入r[l,r]中
merge思想图解：
实际就是将两个有序序列合并
自顶而下归并排序（递归）
java代码：
// 归并排序
public void mergeSort(int[] arr, int start, int end) {
if (start >= end)
return;
int mid = (start + end) / 2;
// 递归排序左边
mergeSort(arr, start, mid);
// 递归排序右边
mergeSort(arr, mid + 1, end);
// 合并
merge(arr, start, mid, end);
}
// 合并两个有序数组
public void merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1]; // 中间数组
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= end) {
temp[k++] = arr[j++];
}
for (p = start; p <= end; p++) {
arr[p] = temp[p];
}
/* for (int p = 0; p < temp.length; p++) {
arr[start + p] = temp[p];
}
*/
}
另一个版本java代码：（类似于算法4书上的表述）
//归并排序
public void sort(int[] arr,int start,int end){
if(start >= end)return;
int mid = start + (end-start)/2;
sort(arr,start,mid);
sort(arr,mid+1,end);
merge(arr,start,mid,end);
}
//合并
public void merge(int[] arr, int start, int mid, int end) {
int i=start,j=mid+1,k=0;
int[] temp = new int[end-start+1];
for(int k=start;k<=end;k++){
if(i>mid)temp[k]=arr[j++];
else if(j>end)temp[k]=arr[i++];
else if(arr[i]>arr[j])temp[k] = arr[j++];
else temp[k] = arr[i++];
}
}
python代码：
def MergeSort(ls):
#合并左右子序列函数
def merge(arr,left,mid,right):
temp=[] #中间数组
i=left #左段子序列起始
j=mid+1 #右段子序列起始
while i<=mid and j<=right:
if arr[i]<=arr[j]:
temp.append(arr[i])
i+=1
else:
temp.append(arr[j])
j+=1
while i<=mid:
temp.append(arr[i])
i+=1
while j<=right:
temp.append(arr[j])
j+=1
for i in range(left,right+1): # !注意这里，不能直接arr=temp,他俩大小都不一定一样
arr[i]=temp[i-left]
#递归调用归并排序
def mSort(arr,left,right):
if left>=right:
return
mid=(left+right)//2
mSort(arr,left,mid)
mSort(arr,mid+1,right)
merge(arr,left,mid,right)
n=len(ls)
if n<=1:
return ls
mSort(ls,0,n-1)
return ls
归并排序划分子问题采用二分法，共需O(logn)次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(nlogn)。
额外空间开销出在合并过程中的一个暂存数组，空间复杂度O(n)。
自底向上的归并排序（非递归）
利用for循环，无递归。但是理解上比较复杂。
快速排序(Quick sort)
特点：
- 原地排序（只需要一个很小的辅助栈）；
- 将长度为 N 的数组排序所需的时间和 NlgN 成正比。
（1）选择待排序记录中第一个记录作为基准，将基准暂存在r[0]的位置上，假设两个指针low和high，初始分别指向表的下界和上界
（2）从表的最右侧位置向左寻找第一个比基准数小的位置，从表的最左侧寻找第一个比基准数大的位置，交换两个元素
（3）重复（2）当low==high时，将基准数放到low位置处的元素判断大于还是小于后，与基准数交换
（4）此时以基准数的位置为分界点，将序列分为两个子序列，分别进行（1），（2），（3）操作，直到序列的长度为1为止
快速排序是一种分治的排序算法。 它的工作原理是将一个数组分成两部分，通过切分实现某一部分总小于另一数组，然后分别独立排序。
切分：一般策略是先随意地选取 a[lo] 作为切分元素，即那个会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。
如此继续，我们就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，我们只需要将切分元素 a[lo] 和左子数组最右侧的元素（a[j]）交换然后返回 j 即可。
java代码：
// 快速排序
public void quickSort(int[] nums, int start, int end) {
if (start >= end)
return;
int partitionIdx = partition(nums, start, end);
quickSort(nums, start, partitionIdx - 1);
quickSort(nums, partitionIdx + 1, end);
}
// partition
public int partition(int[] nums, int start, int end) {
if (start == end) {
return start;
}
int pivot = nums[start];
while (start < end) {
// 从右往左找到第一个小于 pivot 的元素
while (start < end && nums[end] >= pivot) {
end--;
}
// 把小的移动到左边
nums[start] = nums[end];
// 从左往右找到第一个大于 pivot 的元素
while (start < end && nums[start] <= pivot) {
start++;
}
// 把大的移动到右边
nums[end] = nums[start];
}
// 最后把pivot赋值到中间
nums[start] = pivot;
return start;
}
python代码：
def QuickSort(ls):
def partition(arr,left,right):
key=left #划分参考数索引,默认为第一个数，可优化
while left<right:
while left<right and arr[right]>=arr[key]:
right-=1
while left<right and arr[left]<=arr[key]:
left+=1
(arr[left],arr[right])=(arr[right],arr[left])
(arr[left],arr[key])=(arr[key],arr[left])
return left
def quicksort(arr,left,right): #递归调用
if left>=right:
return
mid=partition(arr,left,right)
quicksort(arr,left,mid-1)
quicksort(arr,mid+1,right)
#主函数
n=len(ls)
if n<=1:
return ls
quicksort(ls,0,n-1)
return ls
算法的整体性能取决于划分的平均程度，即基准值的选择，此处衍生出快速排序的许多优化方案，甚至可以划分为多块。
基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。
额外空间开销出在暂存基准值，O(logn)次划分需要O(logn)个，空间复杂度O(logn)。
堆排序(Heap)（优先队列 Priority queues）
可以参考这些文章：
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得当前无序的序列中选择关键字最大（或最小）的记录变得简单，步骤为：
（1）按照堆的定义将待排序序列a[n] 调整为大根堆，这个过程称为初建堆，交换a[1]和a[n] ，则a[n]为关键字的最大记录
（2）将a[n-1]重新调整为堆，交换ra[1]和a[n-1]，此时a[n-1]为关键字最大记录
（3）循环n-1次，直到交换a[1]和a[2]为止
堆排序基于比较交换，是冒泡排序的优化。具体涉及大（小）顶堆的建立与调整。
大顶堆指任意一个父节点都不小于左右两个孩子节点的完全二叉树，根节点最大。
堆排序首先建立大顶堆（找出一个最大值），然后用最后一个叶子结点代替根节点后做大顶堆的调整（再找一个最大值），重复
以数组（列表）实现大顶堆时，从上到下，从左到右编号。父节点序号为n，则左右孩子节点序号分别为2n+1、2n+2
堆的表示：
还有一些基本操作：
上浮（swim）
下沉（sink）
在进行插入和删除元素时都将使用上面两个方法。
python构建堆代码：
def HeapSort(ls):
def heapadjust(arr,start,end): #将以start为根节点的堆调整为大顶堆
temp=arr[start]
son=2*start+1
while son<=end:
if son<end and arr[son]<arr[son+1]: #找出左右孩子节点较大的
son+=1
if temp>=arr[son]: #判断是否为大顶堆
break
arr[start]=arr[son] #子节点上移
start=son #继续向下比较
son=2*son+1
arr[start]=temp #将原堆顶插入正确位置
#######
n=len(ls)
if n<=1:
return ls
#建立大顶堆
root=n//2-1 #最后一个非叶节点（完全二叉树中）
while(root>=0):
heapadjust(ls,root,n-1)
root-=1
#掐掉堆顶后调整堆
i=n-1
while(i>=0):
(ls[0],ls[i])=(ls[i],ls[0]) #将大顶堆堆顶数放到最后
heapadjust(ls,0,i-1) #调整剩余数组成的堆
i-=1
return ls
堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)
额外空间开销出在调整堆过程，根节点下移交换时一个暂存空间，空间复杂度O(1)
参考内容：