常见的排序算法总结
目录
常见排序算法总结
关于排序的部分一直想总结下一直没时间，现在来总结下吧。gif 图来自微信上的文章 (五分钟学算法的公众号，挺不错干货挺多的），原理性的东西就不讲了，图讲的比我好。如果还是不懂可以看看《算法》里面的轨迹图，那个也很直观
冒泡排序
//冒泡排序
private static void MaoPaoSort(int []nums){
for (int i=nums.length-1;i>=0;i--){
for (int j=0;j<i;j++){
if(nums[j]>nums[j+1]){
swap(nums,j,j+1);
}
}
}
}
选择排序
//选择排序
private static void SelectSort(int []nums){
for (int i=0;i<nums.length;i++){
int min=nums[i];
for (int j=i+1;j<nums.length;j++){
if(nums[j]<min){
min=nums[j];
swap(nums,j,i);
}
}
}
}
直接插入排序
//直接插入排序
private static void InsertSort(int []nums){
for (int i=1;i<nums.length;i++){
for (int j=i;j>0&&nums[j]<nums[j-1];j--){
swap(nums,j,j-1);
}
}
}
归并排序
图上面的是递归版本的归并，实现如下
//归并排序
private static void MergerSort(int []nums){
help=new int[nums.length];
MergerSort(nums,0,nums.length-1);
}
private static void MergerSort(int []nums,int left,int right){
if(left>=right){
return;
}
//不能直接在这里创建数组，严重影响性能，可以在上面再套一层方法，或者采用 merger2 的方式（也不好，应该保证辅助数组只初始化一次）
//help=new int[nums.length];
int mid=left+((right-left)>>1);
MergerSort(nums,left,mid);
MergerSort(nums,mid+1,right);
merger(nums,left,mid,right);
}
//辅助数组
private static int []help;
//归并操作
private static void merger(int []nums ,int left,int mid,int right){
int i=left,j=mid+1;
//其实没区别空间复杂度，都是 O(N) 后面这个会更加耗费时间
//int []help=new int[right-left+1];
for (int k=left;k<=right;k++){
//一边的到达尽头，先判断两个边界，不然就要想下面那样写
if(i>mid){
help[k]=nums[j++];
} else if(j>right){
help[k]=nums[i++];
} else if(nums[i]>nums[j]){
help[k]=nums[j++];
} else{
//相等的时候左边先进栈保证稳定性
help[k]=nums[i++];
}
/*// 2
if( i<=mid &&j<=right && nums[i]>nums[j]){
help[k]=nums[j++];
}else if( i<=mid &&j<=right && nums[i]<=nums[j]){
//相等的时候左边先进栈保证稳定性
help[k]=nums[i++];
}else if(i>mid){
help[k]=nums[j++];
}else if(j>right){
help[k]=nums[i++];
}*/
}
//复制
for (int k=left;k<=right;k++){
nums[k]=help[k];
}
/*while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}*/
}
非递归版本
//归并排序（非递归，方向不一样，时间复杂度一样都为 O(NlogN)
private static void MergerSortNoRecurse(int []nums){
help=new int[nums.length];
//控制合并的长度
for (int sz=1;sz<nums.length;sz*=2){
//控制合并的向后移动
for (int i=0;i<nums.length-sz;i+=2*sz){
int r=i+2*sz-1<nums.length-1?i+2*sz-1:nums.length-1;
merger(nums,i,i+sz-1,r);
}
}
}
三向切分的快排（荷兰国旗问题）
//快排 （不具有稳定性或者难以实现）
private static void QuickSort(int []nums,int l,int r){
if(l>r){
return;
}
//随机一个数和 r 交换 ---随机快排
swap(nums, l + (int) (Math.random() * (r - l + 1)), r);
int []index=partition2(nums,l,r);
QuickSort(nums,l,index[0]-1);
QuickSort(nums,index[1]+1,r);
}
public static int partition1(int []nums ,int l,int r){
int base = l;
//双指针
int lo = l, hi = r;
//这种 partition 的实现细节有点不好理解
//这种 partition 不能随机基准元素。
//参照了左神的代码发现其实可以在 partition 之前随机一个变量和 lo 交换，也有同样的效果也消除了输入的影响
while (lo < hi) {
//必须先从右往左，主要是为了归位的时候不出现问题
//比如这里选取的基准元素是 lo 也就是子数组的第一个元素，如果先从左往右最后交换的就是 lo 和一个比 lo 大的数然而比 lo 大的数应该放在右边
//反之如果选的是 hi 为基准就要先从左往右
// 7 0 1 2 10 11 22
while (nums[hi] >= nums[base] && lo < hi) {
hi--;
}
while (nums[lo] <= nums[base] && lo < hi) {
lo++;
}
if (lo < hi) {
swap(nums, lo, hi);
}
}
//归位 lo==hi
swap(nums, hi, base);
return lo;
}
//荷兰国旗优化的快排
public static int[] partition2(int []arr ,int l,int r){
// 7 0 1 2 10 11 22
//小于区为空
int less=l-1;
//l ----> more 为待定区
int more=r;
while(l<more){
if(arr[l]<arr[r]){
swap(arr,++less,l++);
} else if(arr[l]>arr[r]){
//大于基准时 , 大于区扩大（大于区的前一个元素和当前元素交换，但是不知道大于区的前一个元素是什么情况，所以不能 l++)
swap(arr,--more,l);
} else{
l++;
}
}
//和大于区间的第一个交换 保证归位正确，如果选取的是以最左边为基准元素 这里就应该和 less 交换
//到这里 [less+1,more-1] 之间都是等于 基准元素 arr【r】 的
swap(arr,more,r);
//到这 [less+1,more] 之间都是等于 基准元素 arr【r】 的
return new int[]{less+1,more};
}
堆排序
//堆排序
private static void HeapSort(int []nums){
if(nums.length<2){
return;
}
//构建大根堆
for (int i=0; i<nums.length; i++) {
heapInsert(nums,i);
}
//交换堆顶和最后一个节点
int size= nums.length;
swap(nums,size-1,0);
size--;
while(size>1){
//调整
heapIfy(nums,0,size);
//每次都和最后一个孩子节点交换，然后 size--
swap(nums,--size,0);
}
}
//向上爬
private static void heapInsert(int []nums, int index){
//迭代比较当前节点和父节点的值的大小
while(nums[index]>nums[(index-1)/2]){
swap(nums,index,(index-1)/2);
index=(index-1)/2;
}
}
//向下爬
//index 位置的值变小后继续调整为大根堆
private static void heapIfy(int []nums,int index,int size){
//左孩子
int left=index*2+1;
//节点有左孩子
while(left<size){
//判断是否有右孩子。....
//左右孩子里的最大值 有右孩子且右孩子大于左孩子
int largest=left+1<size && nums[left]<nums[left+1] ?left+1:left;
largest=nums[largest]>nums[index]?largest:index;
//最大值等于自己
if(largest==index){
break;
}
//交换大孩子节点和自己
swap(nums,largest,index);
//设置大孩子的 index 和左孩子
index=largest;
left=index*2+1;
}
}
堆排序更优的做法
上面的做法并不是最优的堆排序
public static void heapSort(int []nums){
int last=nums.length-1;
//N 构建大根堆
//从倒数第二层开始
for (int i=nums.length/2-1 ;i>=0;i--){
heapIfy(nums,i,last);
}
//printArray(nums);
while(last>=1){
swap(nums,0,last--);
heapIfy(nums,0,last);
}
}
//i 大根堆调整
public static void heapIfy(int[] nums,int i,int last){
//判断有没有子节点（左孩子）
int left=i*2+1;
while(left<=last){
int right=left+1;
//左右节点最大值
int larger=right<=last && nums[right] > nums[left]?right:left;
if(nums[larger]>nums[i]){
swap(nums,larger,i);
i=larger;
left=larger*2+1;
} else{
break;
}
}
}
public static void swap(int []nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
对比之前的方法，构造堆的方式发生了变化，上面那种通过自上而下的insert方式时间复杂度是O(NlogN)，其实仔细想想，这两种方式是完全相反的，insert 的方式，最后一层每个元素最坏都可能调整logN次，而最后一层也是元素最多的一层，这样一来复杂度就会大大增加，相反如果采用从底向上的heapIfy方式最后一层都只需要调整1次，而根节点需要调整logN次，而根节点只有一个时间复杂度就会大大降低，最终的时间复杂度就是 O(N)，具体推算过程可以看这些回答
手推过程
最后推得到得复杂度是小于O(2N)，也就是O(N)的时间复杂度，如果不是刷leetCode 看到了类似的题可能会一直被那样去写😂
再回首
时隔多年，又回头写了一个，写了大概半个小时左右，边写边回忆，感觉这个写法比上面好一点点，所以记录一下
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int[] nums=new int[N];
for(int i=0;i<N;i++)nums[i]=sc.nextInt();
heapSort(nums);
for(int i=0;i<N;i++)System.out.print(nums[i]+" ");
}
public static void heapSort(int[] nums){
//求左右孩子
// 0
// 1 2
// 3 4 5 6
//7 7/2=3 4/2=1 8/2=4
//O(N) 构建堆
for(int i=nums.length/2;i>=0;i--){ //从 2/n 开始 down 构建二叉树，不一定要精确，多一两个无所谓
down(nums,i,nums.length);
}
int index=0,tail=nums.length;
//堆排，将堆头放到尾部
while(tail>0){
swap(nums,index,--tail);
down(nums,index,tail);
}
}
public static void down(int[] nums,int index,int size){
//求左右孩子
// 0
// 1 2
//3 4 5 6
while(index*2+1 < size){ //还有孩子
int left=index*2+1,right=left+1;
//左右子树中的较大
int largeIndex = right<size && nums[left]<nums[right] ? right:left;
if(nums[index] >= nums[largeIndex]){
return;
}
swap(nums,index,largeIndex);
index=largeIndex;
}
}
public static void swap(int[] nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
}
希尔排序
实际上写排序就是基于插入排序的，在它之上进行了数学上的优化。
实际上从逆序对的角度来看，基于比较的排序就是为了消除逆序对的个数，而诸如冒泡选择每次都只是交换相邻的两个元素，每次交换最多只减少一个逆序对，而希尔排序扩大了这个间距，就增大了减少逆序对的可能。不过要研究他的时间复杂度就是数学上的研究的问题了，至于每次间距都减半这个也是根据大样本测试下这种递增序列性能会更好 O(∩_∩)O
//插入排序的改进
private static void ShellSort(int [] nums){
int h=nums.length>>1;
while(h>0){
for (int i=h;i<nums.length;i++){
//实际上是增大了插入排序的间隙，最后还是对进行一次插入排序，不过那个时候的数据已经是高度有序了
for (int j=i;j-h>=0&&nums[j]<nums[j-h];j-=h) {
swap(nums,j,j-h);
}
}
h=h>>1;
}
}
BUG
排个序还能排出 Bug？对的没错就是排出了 Bug🤣 看看我最开始写的交换函数
private static void swap(int []nums,int a,int b){
nums[a]=nums[a]^nums[b];
nums[b]=nums[a]^nums[b];
nums[a]=nums[a]^nums[b];
}
为了抖这个机灵付出了惨痛的代价，之前用 » 拿来当除 2 操作的时候就忽略了优先级的问题。那这里的机灵有什么问题呢？一个数异或同一个数两次就还原没毛病啊？But 如果交换的两个数是同一个元素比如上面在数组中 a==b 时 nums[a] 异或了 3 次自己相当于nums[a]^nums[a]^nums[a]^nums[a]=0^0=0，最后就会出问题，其实开始前面的排序都没有出现问题，主要是后面的快排时发现了这个 Bug 因为快排为了避免数据分布的影响随机选取基准值，可能随机的是最后一个，而且快排的 partition 过程中也会有时也会自己和自己交换，最开始的第一步就是自己和直接交换，让小于区扩大。所以这个方法仅仅只能用来抖一抖机灵，没啥实际意义，以后还是要老老实实写，不然咋死的都不知道😁
未完待续。….. 还有一类非基于比较的排序 桶排序之类的等后面再来总结加上去。
对数器
直接拿的左神的对数器😄，所有排序都是经过对数器测试的。 talk is cheap show me the code
import java.util.Arrays;
import java.util.Random;
public class Sorts{
public static void main(String[] args) {
/*int []nums={1,0,-1,-22,213,4,535,-112,99999};
//ShellSort(nums);
//MaoPaoSort(nums);
//SelectSort(nums);
//MergerSort(nums,0,nums.length-1);
QuickSort(nums,0,nums.length-1);
printArray(nums);*/
int testTime = 10000;
int maxSize = 10000;
int maxValue = 100;
Boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
long time=System.currentTimeMillis();
//冒泡
//MaoPaoSort(arr1);
//选择
//SelectSort(arr1);
//插入
//InsertSort(arr1);
//归并
//MergerSort(arr1);
//非递归归并
//MergerSortNoRecurse(arr1);
//希尔
//ShellSort(arr1);
//快排
//QuickSort(arr1,0,arr1.length-1);
//堆排序
HeapSort(arr1);
long time2=System.currentTimeMillis();
if(i==0){
System.out.println(time2-time);
}
//系统排序
comparator(arr2);
if(i==0){
System.out.println(System.currentTimeMillis()-time2);
}
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
//初级排序算法
//************************************************************************
//冒泡排序
private static void MaoPaoSort(int []nums){
for (int i=nums.length-1;i>=0;i--){
for (int j=0;j<i;j++){
if(nums[j]>nums[j+1]){
swap(nums,j,j+1);
}
}
}
}
//************************************************************************
//选择排序
private static void SelectSort(int []nums){
for (int i=0;i<nums.length;i++){
int min=nums[i];
for (int j=i+1;j<nums.length;j++){
if(nums[j]<min){
min=nums[j];
swap(nums,j,i);
}
}
}
}
//************************************************************************
//直接插入排序
private static void InsertSort(int []nums){
for (int i=1;i<nums.length;i++){
for (int j=i;j>0&&nums[j]<nums[j-1];j--){
swap(nums,j,j-1);
}
}
}
//************************************************************************
//插入排序的改进
private static void ShellSort(int [] nums){
int h=nums.length>>1;
while(h>0){
for (int i=h;i<nums.length;i++){
//实际上是增大了插入排序的间隙，最后还是对进行一次插入排序，不过那个时候的数据已经是高度有序了
for (int j=i;j-h>=0&&nums[j]<nums[j-h];j-=h) {
swap(nums,j,j-h);
}
}
h=h>>1;
}
}
//************************************************************************
//归并排序
private static void MergerSort(int []nums){
help=new int[nums.length];
MergerSort(nums,0,nums.length-1);
}
private static void MergerSort(int []nums,int left,int right){
if(left>=right){
return;
}
//不能直接在这里创建数组，严重影响性能，可以在上面再套一层方法，或者采用 merger2 的方式（也不好，应该保证辅助数组只初始化一次）
//help=new int[nums.length];
int mid=left+((right-left)>>1);
MergerSort(nums,left,mid);
MergerSort(nums,mid+1,right);
merger(nums,left,mid,right);
}
//辅助数组
private static int []help;
//归并操作
private static void merger(int []nums ,int left,int mid,int right){
int i=left,j=mid+1;
//其实没区别空间复杂度，都是 O(N) 后面这个会更加耗费时间
//int []help=new int[right-left+1];
for (int k=left;k<=right;k++){
//一边的到达尽头，先判断两个边界，不然就要想下面那样写
if(i>mid){
help[k]=nums[j++];
} else if(j>right){
help[k]=nums[i++];
} else if(nums[i]>nums[j]){
help[k]=nums[j++];
} else{
//相等的时候左边先进栈保证稳定性
help[k]=nums[i++];
}
/*// 2
if( i<=mid &&j<=right && nums[i]>nums[j]){
help[k]=nums[j++];
}else if( i<=mid &&j<=right && nums[i]<=nums[j]){
//相等的时候左边先进栈保证稳定性
help[k]=nums[i++];
}else if(i>mid){
help[k]=nums[j++];
}else if(j>right){
help[k]=nums[i++];
}*/
}
//复制
for (int k=left;k<=right;k++){
nums[k]=help[k];
}
//asddsdasdasdasd
/*while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}*/
}
//归并排序（非递归，方向不一样，时间复杂度一样都为 O(NlogN)
private static void MergerSortNoRecurse(int []nums){
help=new int[nums.length];
//控制合并的长度
for (int sz=1;sz<nums.length;sz*=2){
//控制合并的向后移动
for (int i=0;i<nums.length-sz;i+=2*sz){
int r=i+2*sz-1<nums.length-1?i+2*sz-1:nums.length-1;
merger(nums,i,i+sz-1,r);
}
}
}
//************************************************************************
//快排 （不具有稳定性或者难以实现）
private static void QuickSort(int []nums,int l,int r){
if(l>r){
return;
}
//随机一个数和 r 交换 ---随机快排
swap(nums, l + (int) (Math.random() * (r - l + 1)), r);
int []index=partition2(nums,l,r);
QuickSort(nums,l,index[0]-1);
QuickSort(nums,index[1]+1,r);
}
public static int partition1(int []nums ,int l,int r){
int base = l;
//双指针
int lo = l, hi = r;
//这种 partition 的实现细节有点不好理解
//这种 partition 不能随机基准元素。
//参照了左神的代码发现其实可以在 partition 之前随机一个变量和 lo 交换，也有同样的效果也消除了输入的影响
while (lo < hi) {
//必须先从右往左，主要是为了归位的时候不出现问题
//比如这里选取的基准元素是 lo 也就是子数组的第一个元素，如果先从左往右最后交换的就是 lo 和一个比 lo 大的数然而比 lo 大的数应该放在右边
//反之如果选的是 hi 为基准就要先从左往右
// 7 0 1 2 10 11 22
while (nums[hi] >= nums[base] && lo < hi) {
hi--;
}
while (nums[lo] <= nums[base] && lo < hi) {
lo++;
}
if (lo < hi) {
swap(nums, lo, hi);
}
}
//归位 lo==hi
swap(nums, hi, base);
return lo;
}
//荷兰国旗优化的快排
public static int[] partition2(int []arr ,int l,int r){
// 7 0 1 2 10 11 22
//小于区为空
int less=l-1;
//l ----> more 为待定区
int more=r;
while(l<more){
if(arr[l]<arr[r]){
swap(arr,++less,l++);
} else if(arr[l]>arr[r]){
//大于基准时 , 大于区扩大（大于区的前一个元素和当前元素交换，但是不知道大于区的前一个元素是什么情况，所以不能 l++)
swap(arr,--more,l);
} else{
l++;
}
}
//和大于区间的第一个交换 保证归位正确，如果选取的是以最左边为基准元素 这里就应该和 less 交换
//到这里 [less+1,more-1] 之间都是等于 基准元素 arr【r】 的
swap(arr,more,r);
//到这 [less+1,more] 之间都是等于 基准元素 arr【r】 的
return new int[]{less+1,more};
}
//************************************************************************
//堆排序
private static void HeapSort(int []nums){
if(nums.length<2){
return;
}
//构建大根堆
for (int i=0; i<nums.length; i++) {
heapInsert(nums,i);
}
//交换堆顶和最后一个节点
int size= nums.length;
swap(nums,size-1,0);
size--;
while(size>1){
//调整
heapIfy(nums,0,size);
//每次都和最后一个孩子节点交换，然后 size--
swap(nums,--size,0);
}
}
//向上爬
private static void heapInsert(int []nums, int index){
//迭代比较当前节点和父节点的值的大小
while(nums[index]>nums[(index-1)/2]){
swap(nums,index,(index-1)/2);
index=(index-1)/2;
}
}
//向下爬
//index 位置的值变小后继续调整为大根堆
private static void heapIfy(int []nums,int index,int size){
//左孩子
int left=index*2+1;
//节点有左孩子
while(left<size){
//判断是否有右孩子。....
//左右孩子里的最大值 有右孩子且右孩子大于左孩子
int largest=left+1<size && nums[left]<nums[left+1] ?left+1:left;
largest=nums[largest]>nums[index]?largest:index;
//最大值等于自己
if(largest==index){
break;
}
//交换大孩子节点和自己
swap(nums,largest,index);
//设置大孩子的 index 和左孩子
index=largest;
left=index*2+1;
}
}
//************************************************************************
private static void swap(int []nums,int a,int b){
//不知道为啥快排交换的时候这样写会出现很多 0
//查询知道，当 a==b 时自己和直接交换，a 异或自己 4 次后 a==0.....
nums[a]=nums[a]^nums[b];
nums[b]=nums[a]^nums[b];
nums[a]=nums[a]^nums[b];
/*int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;*/
}
// for test 对数器
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
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;
}
// for test
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;
}
// for test
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;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}