[数据结构与算法]常见排序算法[java实现]（面试常考排序算法）

常见排序算法[java实现]（由难到易）

912. 排序数组

快排

• partition

  • 若以起点l为分界线，循环结束r0的含义是从左到右，第一个大于分界线l的下标，交换(l,r0)，并返回下标

  • 注意点

    • left需要保留，含义是分界线的下标

• swap

class Solution {
 ? ?// 快排
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?return quickSort(nums,0,nums.length-1);
 ?  }
 ? ?int[] quickSort(int[] nums, int left, int right)
 ?  {
 ? ? ? ?partition(nums,left,right);
 ? ? ? ?return nums;
 ?  }
 ? ?int partition(int[] nums,int left,int right)
 ?  {
 ? ? ? ?if(left>right) return -1;
 ? ? ? ?int l=left,r=right,divi=nums[l];
 ? ? ? ?while(true)
 ? ? ?  {
 ? ? ? ? ? ?while(l<=r && nums[l]<=divi) l++;
 ? ? ? ? ? ?while(l<=r && nums[r]>divi) r--;
 ? ? ? ? ? ?if(l>r) break;
 ? ? ? ? ? ?swap(nums,l,r);
 ? ? ?  }
 ? ? ? ?swap(nums,left,r);
 ? ? ? ?partition(nums,left,r-1);
 ? ? ? ?partition(nums,r+1,right);
 ? ? ? ?return r;
 ?  }
 ? ?void swap(int[] nums,int l,int r)
 ?  {
 ? ? ? ?int temp = nums[l];
 ? ? ? ?nums[l] = nums[r];
 ? ? ? ?nums[r] = temp;
 ?  }
}

912. 排序数组

归并

• sort

• merge(永远记得，单个函数，就事论事，不干跨权限的事情)

  • 例如最后数组拷贝，起点是left，不是0

  • 例如本次合并，界限为right，不是n-1

class Solution {
 ? ?// 归并排序
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?return sort(nums,0,nums.length-1);
 ?  }
 ? ?public int[] sort(int[] nums,int l,int r)
 ?  {
 ? ? ? ?if(l<r)
 ? ? ?  {
 ? ? ? ? ? ?int mid = (l+r)/2;
 ? ? ? ? ? ?sort(nums,l,mid);
 ? ? ? ? ? ?sort(nums,mid+1,r);
 ? ? ? ? ? ?merge(nums,l,r,mid);
 ? ? ?  }
 ? ? ? ?return nums;
 ?  }
 ? ?void merge(int[] nums,int left,int right,int mid)
 ?  {
 ? ? ? ?int oldL = left;
 ? ? ? ?// System.out.println(Arrays.toString(nums)+ " coming l="+left+" r="+right);
 ? ? ? ?int l = left,r=mid+1;
 ? ? ? ?int[] temp = new int[right-left+1];
 ? ? ? ?int k = 0;
 ? ? ? ?while(l<=mid && r<=right)
 ? ? ?  {
 ? ? ? ? ? ?if(nums[l]<nums[r])
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?temp[k++] = nums[l++];
 ? ? ? ? ?  }else{
 ? ? ? ? ? ? ? ?temp[k++] = nums[r++];
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?while(l<=mid) temp[k++] = nums[l++];
 ? ? ? ?while(r<=right) temp[k++] = nums[r++];
 ? ? ? ?for(int i=0;i<k;i++)
 ? ? ?  {
 ? ? ? ? ? ?nums[left++] = temp[i];
 ? ? ?  }
 ? ? ? ?// System.out.println(Arrays.toString(nums)+ " out l="+oldL+" r="+right);
 ?  }
}

912. 排序数组

计数排序

• 开辟一个values数组，以数组下标来间接表示原数组的元素值，values[i]表示该值出现了多少次

• values长度？

  • values长度最小能表示原数组，为max-min+1

• 数组下标从零开始，如何表示[min,max]的映射空间

  • 数组下标表示num-min,并不是保存原值num

• 那values数组开很大很大，满足映射空间，可以下标直接保存原值吗？

  • 理论上，不可以

    • 原值存在负数，数组溢出

    • num-min，可以将负数转为正值表示

class Solution {
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?int max = Arrays.stream(nums).max().orElseGet(() -> 0);
 ? ? ? ?int min = Arrays.stream(nums).min().orElseGet(() -> 0);
 ? ? ? ?int[] values = new int[max-min+1];
 ? ? ? ?for(int num : nums)
 ? ? ?  {
 ? ? ? ? ? ?values[num-min]++; // 下标位移min
 ? ? ?  }
 ? ? ? ?int k=0;
 ? ? ? ?for(int i=0;i<values.length;i++)
 ? ? ?  {
 ? ? ? ? ? ?while(values[i]>0)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?nums[k++] = i+min;// (i+min)-->原先放入values的值
 ? ? ? ? ? ? ? ?values[i]--;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return nums;
 ?  }
}

912. 排序数组

堆排序：

• 堆：满足一定条件的满二叉树，可以用数组来表示

• 满足的条件：

  • 大根堆：任意非叶子节点i nums[i]>nums[2i+1] && nums[i]>=nums[2i+2]

  • 小根堆：任意非叶子节点i nums[i]<nums[2i+1] && nums[i]<=nums[2i+2]

• 构建堆的下沉操作

  • 其实是根据给定的堆的节点，找该节点正确/合适的位置，也就是满足

    • nums[i]>nums[2i+1] && nums[i]>=nums[2i+2]

  • 具体操作[大根堆为例]

    • 将堆与左右子节点的较大者做比较

      • 若比较大者小，那么子节点与父节点交互，并从新的父节点开始找左右子节点继续判断

      • 若比较大者大，那么下沉操作结束，break

• 堆删除操作[自上而下操作]

  • 移除堆顶元素，实际上是将最后一个元素代替了堆顶元素

  • 移除体现是，堆空间减一

  • 同时，最顶元素下沉操作，找到正确的位置，移除结束

• 堆排序

  • 堆移除操作

    • 每次将堆顶元素与最后一个元素交换位置，堆空间减一

    • 使用downAdjust(nums,0,i-1)，维护堆平衡

class Solution {
 ? ?// 堆排序
 ? ?public static int[] sortArray(int[] arr)
 ?  {
 ? ? ? ?int n = arr.length;
 ? ? ? ?// 构建堆，将前一半元素下沉
 ? ? ? ?for (int i = n; i >=0 ; i--) {
 ? ? ? ? ? ?downAdjust(arr,i,n-1);
 ? ? ?  }
 ? ? ? ?// 每次移除最大值，置于数组尾部
 ? ? ? ?for (int i = n-1; i >=0 ; i--) {
 ? ? ? ? ? ?swap(arr,0,i);
 ? ? ? ? ? ?downAdjust(arr,0,i-1);
 ? ? ?  }
 ? ? ? ?return arr;
 ?  }
?
 ? ?/**
 ? ? *  下沉的过程，其实为了维护堆的性质（nums[i]>nums[2*i+1] && nums[i]>nums[2*i+2]）
 ? ? * @param arr 堆，用数组表示的满二叉树 ?
 ? ? * @param down： 本次下沉的元素下标，找到一个合适的位置，满足左右节点都不大于下沉节点
 ? ? * @param n： 堆的最大节点下标
 ? ? */
 ? ?// downAdjust
 ? ?public static void downAdjust(int[] arr,int down,int n){
 ? ? ? ?if(down>n) return;
 ? ? ? ?int child = 2 * down + 1;
 ? ? ? ?while(child<=n)
 ? ? ?  {
 ? ? ? ? ? ?if(child>n) break; // 此时，下沉节点为叶子节点，不进行下沉
 ? ? ? ? ? ?int right = child+1;
 ? ? ? ? ? ?if(right<=n && arr[right]>arr[child]) // 若right存在，并且比较大，此时最大者为right子节点
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?child = right;
 ? ? ? ? ?  }
 ? ? ? ? ? ?// 是否进行交换，看下沉节点是否比两个子节点还大[大根堆]
 ? ? ? ? ? ?if(arr[down]>=arr[child]) break;
 ? ? ? ? ? ?swap(arr,down,child);
 ? ? ? ? ? ?down = child;
 ? ? ? ? ? ?child = down * 2 + 1;
 ? ? ?  }
 ?  }
 ? ?public static void swap(int[] arr,int l,int r){
 ? ? ? ?int t=arr[l];
 ? ? ? ?arr[l]=arr[r];
 ? ? ? ?arr[r]=t;
 ?  }
}

912. 排序数组

选择排序：超时

• 当前位置，每次循环取最小值，与当前位置交换，只需要N-1次选择

class Solution {
 ? ?public int[] sortArray(int[] arr){
 ? ? ? ?for (int i = 0; i < arr.length - 1; i++) {
 ? ? ? ? ? ?int min = i;
 ? ? ? ? ? ?for (int j = i+1; j < arr.length; j++) {
 ? ? ? ? ? ? ? ?min = (arr[j]<arr[min])?j:min;
 ? ? ? ? ?  }
 ? ? ? ? ? ?swap(arr,i,min);
 ? ? ?  }
 ? ? ? ?return arr;
 ?  }
 ? ?static void swap(int[] arr,int l,int r)
 ?  {
 ? ? ? ?int t = arr[l];
 ? ? ? ?arr[l] = arr[r];
 ? ? ? ?arr[r] = t;
 ?  }
}

912. 排序数组

冒泡排序：超时

• 每次能够将最大值置后，只需要循环N-1次

• 从头往后，逐个判断，将较大值往后交换（交换空间为[0,n-i-1]）

class Solution {
 ? ?public static int[] sortArray(int[] arr){
 ? ? ? ?for (int i = 0; i < arr.length - 1; i++) {
 ? ? ? ? ? ?for (int j = 0; j < arr.length-i-1; j++) {
 ? ? ? ? ? ? ? ?if(arr[j+1]<arr[j])
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? swap(arr,j+1,j); 
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return arr;
 ?  }
 ? ?static void swap(int[] arr,int l,int r)
 ?  {
 ? ? ? ?int t = arr[l];
 ? ? ? ?arr[l] = arr[r];
 ? ? ? ?arr[r] = t;
 ?  }
}

912. 排序数组

插入排序

• 每次ele，插入时，找到离ele最近的比它小的值[j]，插在[j]前面，也就是arr[j+1]=ele

• 比ele大的值往后移动一位 arr[j+1] =arr[j]

class Solution {
 ? ?public static int[] sortArray(int[] nums)
 ?  {
 ? ? ? ?int j=0;
 ? ? ? ?for (int i = 1; i < nums.length; i++) {
 ? ? ? ? ? ?int insert = nums[i];
 ? ? ? ? ? ?for (j = i-1; j >=0 ; j--) {
 ? ? ? ? ? ? ? ?if(nums[j]>insert)
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ?nums[j+1] = nums[j];
 ? ? ? ? ? ? ? ? ? ?continue;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?break;
 ? ? ? ? ?  }
 ? ? ? ? ? ?nums[j+1] = insert;
 ? ? ?  }
 ? ? ? ?return nums;
 ?  }
}

912. 排序数组

基数排序

• 按数字的位数来分类，分类N次，N为数中最大值的位数

• 由于存在负数的情况，所以在分类前，需要将元素转为正数，num-min即可，返回时，追加min恢复原值，加减同一个值并不改变排序结果

class Solution {
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?return sort(nums);
 ?  }
 ? ?public static int[] sort(int[] arr)
 ?  {
 ? ? ? ?// 1. 预处理arr，让arr全部都是正数
 ? ? ? ?int min = Arrays.stream(arr).min().getAsInt();
 ? ? ? ?arr = Arrays.stream(arr).map(ar -> ar - min).toArray();
 ? ? ? ?// 2. 计算arr中最大值的位数bit
 ? ? ? ?int max = Arrays.stream(arr).max().getAsInt();
 ? ? ? ?int bit = getBit(max);
 ? ? ? ?// 3. 初始化基数桶
 ? ? ? ?ArrayList<LinkedList<Integer>> bucket = new ArrayList<>(10);
 ? ? ? ?for (int i = 0; i < 10; i++) {
 ? ? ? ? ? ?bucket.add(new LinkedList<>());
 ? ? ?  }
 ? ? ? ?int bi = 1;
 ? ? ? ?// 4. 循环bit次
 ? ? ? ?for (int i = 0; i < bit; i++) {
 ? ? ? ? ? ?// 将数组元素放入bucket,以当前的基数为下标
 ? ? ? ? ? ?for (int j = 0; j < arr.length; j++) {
 ? ? ? ? ? ? ? ?int index = (arr[j] / bi) % 10;
 ? ? ? ? ? ? ? ?bucket.get(index).add(arr[j]);
 ? ? ? ? ?  }
 ? ? ? ? ? ?int k = 0;
 ? ? ? ? ? ?// 将桶数据依次回流数组
 ? ? ? ? ? ?for (LinkedList<Integer> buck : bucket) {
 ? ? ? ? ? ? ? ?for (Integer num : buck) {
 ? ? ? ? ? ? ? ? ? ?arr[k++] = num;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ? ? ?// 桶清空
 ? ? ? ? ? ? ? ?buck.clear();
 ? ? ? ? ?  }
 ? ? ? ? ? ?bi*=10;
 ? ? ?  }
 ? ? ? ?// 最后返回时，需要将arr的值转回去
 ? ? ? ?arr = Arrays.stream(arr).map(ar->ar+min).toArray();
 ? ? ? ?return arr;
 ?  }
 ? ?static int getBit(int num)
 ?  {
 ? ? ? ?if(num==0) return 1;
 ? ? ? ?int bit=0;
 ? ? ? ?while (num!=0)
 ? ? ?  {
 ? ? ? ? ? ?bit++;
 ? ? ? ? ? ?num/=10;
 ? ? ?  }
 ? ? ? ?return bit;
 ?  }
}

912. 排序数组

桶排

• 桶排序类似于计数排序，但是它能解决比计数排序更多问题，例如区间偏移量大，或者浮点数排序计数排序无法映射到数组下标，但是桶排序可以做好，它并不是以下标为映射，而是通过将数组数值区间 [min,max]划分为多个小区间，元素通过计算与区间的偏移量，定位到某个区间，小区间与小区间之间有序，那么小区间独立排序后合并也有序，大而化之

class Solution {
 ? ?// 桶排序
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?return sort(nums);
 ?  }
 ? ?public static int[] sort(int[] nums)
 ?  {
 ? ? ? ?// set
 ? ? ? ?Set<Integer> set = new HashSet<>();
 ? ? ? ?// 数值区间[min,max]分为block块，分别排序后，合并
 ? ? ? ?int min = Arrays.stream(nums).min().getAsInt();
 ? ? ? ?int max = Arrays.stream(nums).max().getAsInt();
 ? ? ? ?// 定义block块
 ? ? ? ?int block = nums.length;
 ? ? ? ?// 每个小区间
 ? ? ? ?int d = (max-min)/block;
 ? ? ? ?// 
 ? ? ? ?int total = Math.max(max-min,1);
 ? ? ? ?// 定义block个桶
 ? ? ? ?List<List<Integer>> bucket = new ArrayList<>(block);
 ? ? ? ?for(int i=0;i<block;i++) bucket.add(new LinkedList());
 ? ? ? ?// 将数据按照大小区间入桶
 ? ? ? ?for(int num : nums)
 ? ? ?  {
 ? ? ? ? ? ?int index = (num-min)/(d+1); // (num-min)-->当前元素相对于min的偏移量，偏移量除以d+1-->向下取整
 ? ? ? ? ? ?set.add(index);
 ? ? ? ? ? ?bucket.get(index).add(num);
 ? ? ?  }
 ? ? ? ?// 将每个桶排序，并收集结果
 ? ? ? ?int k = 0;
 ? ? ? ?for(List<Integer> path : bucket)
 ? ? ?  {
 ? ? ? ? ? ?Collections.sort(path);
 ? ? ? ? ? ?for(int val : path)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?nums[k++] = val;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return nums;
 ?  }
}

912. 排序数组

希尔排序

• 希尔排序本质上是对插入排序的增强，分组插入的思想

• 每次排序，以gap为间隔，插入排序，例如元素i的前一个元素为i-gap

• 当gap==0时，没有间距，排序完成

class Solution {
 ? ?public int[] sortArray(int[] nums) {
 ? ? ? ?// 分组插入
 ? ? ? ?int n = nums.length;
 ? ? ? ?// 分组
 ? ? ? ?int gap = n/2;
 ? ? ? ?while(gap>=1)
 ? ? ?  {
 ? ? ? ? ? ?for(int i=gap;i<n;i++)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?insert(nums,gap,i); //以gap的间距，构成的组，插入排序
 ? ? ? ? ?  }
 ? ? ? ? ? ?gap/=2;
 ? ? ?  }
 ? ? ? ?return nums;
 ?  }
 ? ?static void insert(int[] nums,int gap,int insert)
 ?  {
 ? ? ? ?int temp = nums[insert];
 ? ? ? ?int j;
 ? ? ? ?for(j=insert-gap;j>=0;j-=gap)
 ? ? ?  {
 ? ? ? ? ? ?if(temp<nums[j]) nums[j+gap] = nums[j];
 ? ? ? ? ? ?else break;
 ? ? ?  }
 ? ? ? ?nums[j+gap] = temp; ? 
 ?  }
}