网站导航
> 技术文档 > Java 排序

Java 排序

网友: 技术文档 2025-07-30 12:28:57

文章目录

  • 排序
    • 插入排序
      • 分析
    • 希尔排序
      • 分析
    • 选择排序
      • 分析
    • 堆排序
      • 分析
    • 冒泡排序
      • 分析
    • 快速排序
      • 霍尔法
      • 分析
      • 挖坑法找基准
      • 前后指针法
      • 题目
      • 快排的优化
        • 三数取中法
      • 非递归实现快排
    • 归并排序
      • 分析
      • 非递归实现归并排序
    • 海量数据的排序
    • 非比较的排序
      • 计数排序
      • 分析
      • 基数排序
      • 桶排序

Java 排序

排序

  1. 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
  2. 内部排序：在内存上的排序
  3. 外部排序：需要借助磁盘等外部空间进行的排序

插入排序

  1. 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入

Java 排序

// 插入排序 public static void insertSort(int[] array){ for(int i = 1;i < array.length;i++){ int j = i - 1; int tmp = array[i]; for(;j >= 0;j--){ if(array[j] > tmp){  array[j+1] = array[j]; }else{  break; } } array[j + 1] = tmp; } }

分析

  1. 时间复杂度：O(N^2)
    最坏情况：O(N^2)
    最好情况：有序的数组，O(N)
    数据越有序，排序越快
    适用于待排序数组基本上趋于有序了，时间复杂度趋于O(N)
  2. 空间复杂度：O(1)
  3. 稳定性：是一个稳定的排序
    例子：5 5 7
    稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序

希尔排序

  1. 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为O(N^2)
  2. 分组：分完组后，每组都采用直接插入排序
  3. 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
  4. 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的5 3 都是预排序，真正的排序是最后的一组
  5. 缩小增量的目的：为了让排序更接近O(N)，为了让排序更快

Java 排序
Java 排序

// 希尔排序 public static void shellSort(int[] array){ int gap = array.length; while(gap > 1){ gap /= 2; shell(array,gap); } } // 对每组进行插入排序 public static void shell(int[] array,int gap){ for(int i = gap;i < array.length;i++){ int j = i - gap; int tmp = array[i]; for(;j >= 0;j -= gap){ if(array[j] > tmp){  array[j+gap] = array[j]; }else{  break; } } array[j + gap] = tmp; } }

分析

  1. 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

检测排序速度：

public static void testInsert(int[] array){ long startTime = System.currentTimeMillis(); int[] tmp = Arrays.copyOf(array,array.length); Sort.insertSort(tmp); long endTime = System.currentTimeMillis(); System.out.println(\" \" + (endTime - startTime)); } public static void testShell(int[] array){ long startTime = System.currentTimeMillis(); int[] tmp = Arrays.copyOf(array,array.length); Sort.shellSort(tmp); long endTime = System.currentTimeMillis(); System.out.println(\" \" + (endTime - startTime)); } // 逆序初始化 public static void initOrder(int[] array){ for(int i = 0;i < array.length;i++){ array[i] = array.length - i; } } public static void main(String[] args) { int[] arr = new int[10000]; initOrder(arr); testInsert(arr); testShell(arr); }

选择排序

  1. 在当前i下标对应的值的后面，找到后面最小的值和i下标对应的值交换
    Java 排序
// 交换 public static void swap(int i, int j, int[] array){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } // 选择排序 public static void selectSort(int[] array){ // 在i下标的后面找到比i下标对应的值的最小值,然后交换 int n = array.length; for(int i = 0;i < n;i++){ int minIndex = i; for(int j = i + 1;j < n;j++){ if(array[j] < array[i]){  if(array[j] < array[minIndex]){ minIndex = j;  } } } swap(i,minIndex,array); } }
  1. 双向选择排序
    时间复杂度还是O(N^2)
    左边找最大的，右边找最小的，和第一个数和最后一个数交换
    Java 排序
    存在缺陷，maxIndex下标可能是在0下标是最大的，0下标会和最小值小标的值交换，那么0下标就不是最大值下标，应该更新为maxIndex = minIndex

Java 排序

public static void selectSort2(int[] array){ // 在i下标的后面找到比i下标对应的值的最小值,然后交换 int left = 0; int right = array.length - 1; while(left < right){ int minIndex = left; int maxIndex = left; for(int i = left + 1;i <= right;i++){ if(array[i] < array[minIndex]){  minIndex = i; } if(array[i] > array[maxIndex]){  maxIndex = i; } } swap(left,minIndex,array); // 第一个数是最大的数,防止最小的下标和第一个数换了,最大值就在minIndex的位置了 if(maxIndex == left){ maxIndex = minIndex; } swap(right,maxIndex,array); left++; right--; } }

分析

  1. 时间复杂度：O(N^2)
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

堆排序

// 堆排序 private static void shifDown(int[] array,int parent,int len){ int child = 2 * parent + 1; while(child < len){ if(child + 1 < len && array[child] < array[child + 1]){ child++; } if(array[child] > array[parent]){ swap(child,parent,array); parent = child; child = 2 * parent + 1; }else{ break; } } } private static void createHeap(int[] array){ // 建立大根堆 for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--) { shifDown(array, parent, array.length); } } public static void heapSort(int[] array){ createHeap(array); int end = array.length - 1; while(end > 0){ swap(end,0,array); shifDown(array,0,end); end--; } }

分析

  1. 时间复杂度：O(N * logN)
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定的排序

冒泡排序

// 冒泡排序 public static void bubbleSort(int[] array){ // i是趟数 for(int i = 0;i < array.length;i++){ // j是比较的大小的 boolean flag = true; for(int j = 0;j < array.length - i - 1;j++){ if(array[j] > array[j + 1]){  swap(j,j + 1,array);  flag = false; } } if(flag) { break; } } }

分析

  1. 时间复杂度：O(N ^ 2)
  2. 空间复杂度：O(1)
  3. 稳定性：稳定的排序

快速排序

霍尔法

  1. 根据二叉树进行递归划分

Java 排序

// 快速排序 public static void quickSort(int[] array){ quick(array,0,array.length - 1); } private static void quick(int[] array,int start,int end){ if(start >= end){ return; } int prvot = partitionHoare(array,start,end); quick(array,start,prvot - 1); quick(array,prvot + 1,end); } private static int partitionHoare(int[] array,int left,int right){ // 基准元素 int tmp = array[left]; // 记录第一个基准下标 int i = left; while(left < right) { // 必须先找先右再左 // 找小 while (left < right && array[right] >= tmp) { right--; } // 找大 while (left < right && array[left] <= tmp) { left++; } swap(left, right, array); } swap(i,left,array); return left; }
  1. 为什么有等于号？
    没有等于号，会死循环，比如两端都是6

Java 排序

  1. 为什么先从右边开始，不先从左边开始？
    先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6的左边有一个数比6大
    Java 排序

分析

  1. 时间复杂度：
    最好情况下：O(N * logN)
    每层都有N个节点，高度为logN，需要每个节点都遍历到，N * logN次遍历
    最坏情况下：O(N^2)，有序/逆序，单分支的树
  2. 空间复杂度：
    最好情况下：O(logN)
    最坏情况下：O(N)，有序/逆序，单分支的树
    递归左边再递归右边，递归右边左边没有释放
  3. 稳定性：不稳定的排序

挖坑法找基准

  1. 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中
// 挖坑法 private static int partitionHole(int[] array,int left,int right){ // 基准元素 int tmp = array[left]; while(left < right) { // 必须先找先右再左 // 找小 while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; // 找大 while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; }

前后指针法

  1. 如果cur比基准元素小并且cur下标的值和prev下标的值不相等，

Java 排序

// 前后指针法 public static int partition(int[] array,int left,int right){ int prev = left; int cur = left + 1; while(cur <= right){ while(array[cur] < array[left] && array[++prev] != array[cur]){ swap(cur,prev,array); } cur++; } swap(prev,left,array); return prev; }

题目

  1. 优先试挖坑法，其次是Hoare，最后是前后指针法

A

Java 排序

快排的优化

  1. 均匀的分割数组
  2. 让递归的次数变少
三数取中法
  1. 三数取中法：left，right，mid三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值
  2. 规定array[mid] <= array[left] <= array[right]
    Java 排序
// 三数取中法,求中位数的下标 private static int middleNum(int[] array,int left,int right){ int mid = (left + right) / 2; if(array[left] < array[right]){ // 1. x < 3 < 9 // 2. 3 < 9 < x // 3. 3 < x < 9 if(array[mid] < array[left]){ return left; } else if(array[mid] > array[right]){ return right; } else{ return mid; } }else{ // 9 > 3 == left > right // 1. x > left > right if(array[mid] > array[left]){ return left; }else if(array[right] > array[mid]){ // 2. left > right > x return right; }else{ // 3. left > x > right return mid; } } } private static void quick(int[] array,int start,int end){ if(start >= end){ return; } // 1 2 3 4 5 6 7 // 中间值的下标和第一个数交换,作为新的基准元素 int index = middleNum(array,start,end); swap(index,start,array); // 4 2 3 1 5 6 7 // 为了让左右分布更均匀,降低树的高度,减少递归的次数 int prvot = partition(array,start,end); quick(array,start,prvot - 1); quick(array,prvot + 1,end); }

只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了

public static void insertSort(int[] array,int left,int right){ for(int i = left + 1;i <= right;i++){ int j = i - 1; int tmp = array[i]; for(;j >= left;j--){ if(array[j] > tmp){  array[j+1] = array[j]; }else{  break; } } array[j + 1] = tmp; } } private static void quick(int[] array,int start,int end){ if(start >= end){ return; } if(end - start + 1 <= 15){ // 减少递归的次数 // 因为最后几层节点数最多,递归次数也多 insertSort(array,start,end); return; } // 1 2 3 4 5 6 7 // 中间值的下标和第一个数交换,作为新的基准元素 int index = middleNum(array,start,end); swap(index,start,array); // 4 2 3 1 5 6 7 // 为了让左右分布更均匀,降低树的高度,减少递归的次数 int prvot = partition(array,start,end); quick(array,start,prvot - 1); quick(array,prvot + 1,end); }

非递归实现快排

  1. 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置

Java 排序

 // 非递归实现快速排序 public static void quickSortNor(int[] array){ int start = 0; int end = array.length - 1; Stack<Integer> stack = new Stack<>(); int pivot = partitionHoare(array,start,end); if(pivot - 1 > start){ // 左边有两个元素 stack.push(start); stack.push(pivot - 1); } else if(pivot + 1 < end){ // 右边至少有两个元素 stack.push(pivot + 1); stack.push(end); } // 找基准里面会互换元素进行排序 while(!stack.empty()){ end = stack.pop(); start = stack.pop(); pivot = partitionHoare(array,start,end); if(pivot - 1 > start){ // 左边有两个元素 stack.push(start); stack.push(pivot - 1); } else if(pivot + 1 < end){ // 右边至少有两个元素 stack.push(pivot + 1); stack.push(end); } }

归并排序

  1. 分解：根据mid进行分解

  2. 合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中
    Java 排序

// 归并排序 public static void mergeSort(int[] array){ merge(array,0,array.length - 1); } private static void merge(int[] array,int start,int end){ if(start >= end){ return; } int mid = (start + end) / 2; // 分解 merge(array,start,mid); merge(array,mid + 1,end); // 合并 mergeHeB(array,start,mid,end); } private static void mergeHeB(int[] array, int left, int mid, int right) { int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; // 新数组的下标 int k = 0; int[] tmpArray = new int[right - left + 1]; while(s1 <= e1 && s2 <= e2){ if(array[s1] < array[s2]){ tmpArray[k++] = array[s1++]; }else{ tmpArray[k++] = array[s2++]; } } while(s1 <= e1){ tmpArray[k++] = array[s1++]; } while(s2 <= e2){ tmpArray[k++] = array[s2++]; } // left是因为有左边还有右边的数组 // tmpArray是临时数组,会销毁的,需要拷贝回原来的数组 for(int i = 0;i < tmpArray.length;i++){ array[i + left] = tmpArray[i]; } }

分析

  1. 时间复杂度：O(N * logN)
  2. 空间复杂度：O(N)，因为每次合并数组的时候要开O(N)大小的额外空间
  3. 稳定性：稳定的排序

非递归实现归并排序

  1. 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
  2. gap = 1
    left = i
    mid = left + gap - 1
    right = mid + gap
    gap *= 2
  3. 每组合并完，最终就有序了

Java 排序

// 非递归实现归并排序 public static void mergeSortNor(int[] array){ // gap表示每组的数据个数 int gap = 1; while(gap < array.length){ for(int i = 0;i < array.length;i = i + 2 * gap){ int left = i; // mid和right可能会越界 // 比如只有5个元素 // 分解右边一半的时候 // l = i mid = 5 r = 7 int mid = left + gap - 1; int right = mid + gap; if(mid >= array.length){  mid = array.length - 1; } if(right >= array.length){  right = array.length - 1; } mergeHeB(array,left,mid,right); } gap *= 2; } }

海量数据的排序

  1. 使用归并排序进行外部排序，如果内存中不够空间的话

Java 排序

非比较的排序

计数排序

  1. 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
  2. 适用的场景：指定范围内的数据

Java 排序

// 计数排序,指定范围内的数据进行排序// O(Max(N，范围)) public static void countSort(int[] array){ int minVal = array[0]; int maxVal = array[0]; // O(N) for(int i = 0;i < array.length;i++){ if(minVal > array[i]){ minVal = array[i]; } if(maxVal < array[i]){ maxVal = array[i]; } } int len = maxVal - minVal + 1; int[] count = new int[len]; // O(N) for(int i = 0;i < array.length;i++){ count[array[i] - minVal]++; } // 写回array数组中 // O(范围) // 因为count数组集中于一个数字,那么也是O(范围) // 如果count数组不集中于一个数子,也是N倍的范围 // 也是O(范围) int k = 0; for(int i = 0;i < count.length;i++){ while(count[i] > 0){ array[k++] = i + minVal; count[i]--; } } }

分析

  1. 时间复杂度：O(Max(N，范围))
  2. 空间复杂度：O(范围)
  3. 稳定性：稳定的排序

基数排序

  1. 开10个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列

Java 排序

桶排序

  1. 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了

Java 排序

网络标签：

相关问题