排序算法汇总以及java实现

排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。运行快、原地、稳定、自适应、通用性好。显然，迄今为止尚未发现兼具以上所有特性的排序算法。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定。
1，选择排序：选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

/* 选择排序 */voidselectionSort(int[]nums){intn=nums.length;// 外循环：未排序区间为 [i, n-1]for(inti=0;i<n-1;i++){// 内循环：找到未排序区间内的最小元素intk=i;for(intj=i+1;j<n;j++){if(nums[j]<nums[k])k=j;// 记录最小元素的索引}// 将该最小元素与未排序区间的首个元素交换inttemp=nums[i];nums[i]=nums[k];nums[k]=temp;}}

2，冒泡排序：通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

/* 冒泡排序 */voidbubbleSort(int[]nums){// 外循环：未排序区间为 [0, i]for(inti=nums.length-1;i>0;i--){// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for(intj=0;j<i;j++){if(nums[j]>nums[j+1]){// 交换 nums[j] 与 nums[j + 1]inttmp=nums[j];nums[j]=nums[j+1];nums[j+1]=tmp;}}}}

3，插入排序：是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

/* 插入排序 */voidinsertionSort(int[]nums){// 外循环：已排序区间为 [0, i-1]for(inti=1;i<nums.length;i++){intbase=nums[i],j=i-1;// 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置while(j>=0&&nums[j]>base){nums[j+1]=nums[j];// 将 nums[j] 向右移动一位j--;}nums[j+1]=base;// 将 base 赋值到正确位置}}

4，快速排序：是一种基于分治策略的排序算法，运行高效，应用广泛。
核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

/* 元素交换 */voidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}/* 哨兵划分 */intpartition(int[]nums,intleft,intright){// 以 nums[left] 为基准数inti=left,j=right;while(i<j){while(i<j&&nums[j]>=nums[left])j--;// 从右向左找首个小于基准数的元素while(i<j&&nums[i]<=nums[left])i++;// 从左向右找首个大于基准数的元素swap(nums,i,j);// 交换这两个元素}swap(nums,i,left);// 将基准数交换至两子数组的分界线returni;// 返回基准数的索引}

5，归并排序（merge sort）是一种基于分治策略的排序算法，包含“划分”和“合并”阶段。划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

/* 合并左子数组和右子数组 */voidmerge(int[]nums,intleft,intmid,intright){// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]// 创建一个临时数组 tmp ，用于存放合并后的结果int[]tmp=newint[right-left+1];// 初始化左子数组和右子数组的起始索引inti=left,j=mid+1,k=0;// 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中while(i<=mid&&j<=right){if(nums[i]<=nums[j])tmp[k++]=nums[i++];elsetmp[k++]=nums[j++];}// 将左子数组和右子数组的剩余元素复制到临时数组中while(i<=mid){tmp[k++]=nums[i++];}while(j<=right){tmp[k++]=nums[j++];}// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间for(k=0;k<tmp.length;k++){nums[left+k]=tmp[k];}}/* 归并排序 */voidmergeSort(int[]nums,intleft,intright){// 终止条件if(left>=right)return;// 当子数组长度为 1 时终止递归// 划分阶段intmid=left+(right-left)/2;// 计算中点mergeSort(nums,left,mid);// 递归左子数组mergeSort(nums,mid+1,right);// 递归右子数组// 合并阶段merge(nums,left,mid,right);}

6，堆排序（heap sort）：是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。输入数组并建立小顶堆，此时最小元素位于堆顶。不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */voidsiftDown(int[]nums,intn,inti){while(true){// 判断节点 i, l, r 中值最大的节点，记为 maintl=2*i+1;intr=2*i+2;intma=i;if(l<n&&nums[l]>nums[ma])ma=l;if(r<n&&nums[r]>nums[ma])ma=r;// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出if(ma==i)break;// 交换两节点inttemp=nums[i];nums[i]=nums[ma];nums[ma]=temp;// 循环向下堆化i=ma;}}/* 堆排序 */voidheapSort(int[]nums){// 建堆操作：堆化除叶节点以外的其他所有节点for(inti=nums.length/2-1;i>=0;i--){siftDown(nums,nums.length,i);}// 从堆中提取最大元素，循环 n-1 轮for(inti=nums.length-1;i>0;i--){// 交换根节点与最右叶节点（交换首元素与尾元素）inttmp=nums[0];nums[0]=nums[i];nums[i]=tmp;// 以根节点为起点，从顶至底进行堆化siftDown(nums,i,0);}}

7，桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

/* 桶排序 */voidbucketSort(float[]nums){// 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素intk=nums.length/2;List<List<Float>>buckets=newArrayList<>();for(inti=0;i<k;i++){buckets.add(newArrayList<>());}// 1. 将数组元素分配到各个桶中for(floatnum:nums){// 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]inti=(int)(num*k);// 将 num 添加进桶 ibuckets.get(i).add(num);}// 2. 对各个桶执行排序for(List<Float>bucket:buckets){// 使用内置排序函数，也可以替换成其他排序算法Collections.sort(bucket);}// 3. 遍历桶合并结果inti=0;for(List<Float>bucket:buckets){for(floatnum:bucket){nums[i++]=num;}}}

8，计数排序（counting sort）：通过统计元素数量来实现排序，通常应用于整数数组。

/* 计数排序 */// 完整实现，可排序对象，并且是稳定排序voidcountingSort(int[]nums){// 1. 统计数组最大元素 mintm=0;for(intnum:nums){m=Math.max(m,num);}// 2. 统计各数字的出现次数// counter[num] 代表 num 的出现次数int[]counter=newint[m+1];for(intnum:nums){counter[num]++;}// 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”// 即 counter[num]-1 是 num 在 res 中最后一次出现的索引for(inti=0;i<m;i++){counter[i+1]+=counter[i];}// 4. 倒序遍历 nums ，将各元素填入结果数组 res// 初始化数组 res 用于记录结果intn=nums.length;int[]res=newint[n];for(inti=n-1;i>=0;i--){intnum=nums[i];res[counter[num]-1]=num;// 将 num 放置到对应索引处counter[num]--;// 令前缀和自减 1 ，得到下次放置 num 的索引}// 使用结果数组 res 覆盖原数组 numsfor(inti=0;i<n;i++){nums[i]=res[i];}}

9，基数排序（radix sort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */intdigit(intnum,intexp){// 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算return(num/exp)%10;}/* 计数排序（根据 nums 第 k 位排序） */voidcountingSortDigit(int[]nums,intexp){// 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组int[]counter=newint[10];intn=nums.length;// 统计 0~9 各数字的出现次数for(inti=0;i<n;i++){intd=digit(nums[i],exp);// 获取 nums[i] 第 k 位，记为 dcounter[d]++;// 统计数字 d 的出现次数}// 求前缀和，将“出现个数”转换为“数组索引”for(inti=1;i<10;i++){counter[i]+=counter[i-1];}// 倒序遍历，根据桶内统计结果，将各元素填入 resint[]res=newint[n];for(inti=n-1;i>=0;i--){intd=digit(nums[i],exp);intj=counter[d]-1;// 获取 d 在数组中的索引 jres[j]=nums[i];// 将当前元素填入索引 jcounter[d]--;// 将 d 的数量减 1}// 使用结果覆盖原数组 numsfor(inti=0;i<n;i++)nums[i]=res[i];}/* 基数排序 */voidradixSort(int[]nums){// 获取数组的最大元素，用于判断最大位数intm=Integer.MIN_VALUE;for(intnum:nums)if(num>m)m=num;// 按照从低位到高位的顺序遍历for(intexp=1;exp<=m;exp*=10){// 对数组元素的第 k 位执行计数排序// k = 1 -> exp = 1// k = 2 -> exp = 10// 即 exp = 10^(k-1)countingSortDigit(nums,exp);}}