devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣解题：数组排序 各种排序算法 java_力扣有默认排序方法

作者：一键难忘520 | 2024-06-19 07:59:31

赞

踩

力扣有默认排序方法

题目：

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：输入：nums = [5,2,3,1] 输出：[1,2,3,5]

1、直接插入排序

  1. /*nums[]数组，对其升序排序
  2. * */
  3. //插入排序
  4. public class InsertSort {
  5.     public int[] sortArray(int[] nums) {
  6.         int len = nums.length;
  7.         for (int i = 1; i < len; i++) {
  8.             // 先暂存这个元素，然后之前元素逐个后移，留出空位
  9.             if (nums[i]<nums[i-1]) {
  10.                 int temp = nums[i];
  11.                 int j = i - 1;
  12.                 while (j >= 0 && nums[j] > temp) {
  13.                     nums[j + 1] = nums[j];
  14.                     j--;
  15.                 }
  16.                 nums[j + 1] = temp;
  17.             }
  18.         }
  19.         return nums;
  20.     }
  21.  
  22.  
  23. }

2、选择排序

  1. public class Solution {
  2.  
  3.     // 选择排序：每一轮选择最小元素交换到未排定部分的开头
  4.  
  5.     public int[] sortArray(int[] nums) {
  6.         int len = nums.length;
  7.         // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
  8.         for (int i = 0; i < len - 1; i++) {
  9.             // 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
  10.             int minIndex = i;
  11.             for (int j = i + 1; j < len; j++) {
  12.                 if (nums[j] < nums[minIndex]) {
  13.                     minIndex = j;
  14.                 }
  15.             }
  16.             swap(nums, i, minIndex);
  17.         }
  18.         return nums;
  19.     }
  20.  
  21.     private void swap(int[] nums, int index1, int index2) {
  22.         int temp = nums[index1];
  23.         nums[index1] = nums[index2];
  24.         nums[index2] = temp;
  25.     }
  26.  
  27.     public static void main(String[] args) {
  28.         int[] nums = {5, 2, 3, 1};
  29.         Solution solution = new Solution();
  30.         int[] res = solution.sortArray(nums);
  31.         System.out.println(Arrays.toString(res));
  32.     }
  33. }

3、归并排序

  1. public class Solution {
  2.     // 归并排序
  3.  
  4.     /**
  5.      * 列表大小等于或小于该大小，将优先于 mergeSort 使用插入排序
  6.      */
  7.     private static final int INSERTION_SORT_THRESHOLD = 7;
  8.  
  9.     public int[] sortArray(int[] nums) {
  10.         int len = nums.length;
  11.         int[] temp = new int[len];
  12.         mergeSort(nums, 0, len - 1, temp);
  13.         return nums;
  14.     }
  15.  
  16.     /**
  17.      * 对数组 nums 的子区间 [left, right] 进行归并排序
  18.      *
  19.      * @param nums
  20.      * @param left
  21.      * @param right
  22.      * @param temp  用于合并两个有序数组的辅助数组，全局使用一份，避免多次创建和销毁
  23.      */
  24.     private void mergeSort(int[] nums, int left, int right, int[] temp) {
  25.         // 小区间使用插入排序
  26.         if (right - left <= INSERTION_SORT_THRESHOLD) {
  27.             insertionSort(nums, left, right);
  28.             return;
  29.         }
  30.  
  31.         int mid = left + (right - left) / 2;
  32.         // Java 里有更优的写法，在 left 和 right 都是大整数时，即使溢出，结论依然正确
  33.         // int mid = (left + right) >>> 1;
  35.         mergeSort(nums, left, mid, temp);
  36.         mergeSort(nums, mid + 1, right, temp);
  37.         // 如果数组的这个子区间本身有序，无需合并
  38.         if (nums[mid] <= nums[mid + 1]) {
  39.             return;
  40.         }
  41.         mergeOfTwoSortedArray(nums, left, mid, right, temp);
  42.     }
  43.  
  44.     /**
  45.      * 对数组 arr 的子区间 [left, right] 使用插入排序
  46.      *
  47.      * @param arr   给定数组
  48.      * @param left  左边界，能取到
  49.      * @param right 右边界，能取到
  50.      */
  51.     private void insertionSort(int[] arr, int left, int right) {
  52.         for (int i = left + 1; i <= right; i++) {
  53.             int temp = arr[i];
  54.             int j = i;
  55.             while (j > left && arr[j - 1] > temp) {
  56.                 arr[j] = arr[j - 1];
  57.                 j--;
  58.             }
  59.             arr[j] = temp;
  60.         }
  61.     }
  62.  
  63.     /**
  64.      * 合并两个有序数组：先把值复制到临时数组，再合并回去
  65.      *
  66.      * @param nums
  67.      * @param left
  68.      * @param mid   [left, mid] 有序，[mid + 1, right] 有序
  69.      * @param right
  70.      * @param temp  全局使用的临时数组
  71.      */
  72.     private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
  73.         System.arraycopy(nums, left, temp, left, right + 1 - left);
  74.  
  75.         int i = left;
  76.         int j = mid + 1;
  77.  
  78.         for (int k = left; k <= right; k++) {
  79.             if (i == mid + 1) {
  80.                 nums[k] = temp[j];
  81.                 j++;
  82.             } else if (j == right + 1) {
  83.                 nums[k] = temp[i];
  84.                 i++;
  85.             } else if (temp[i] <= temp[j]) {
  86.                 // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
  87.                 nums[k] = temp[i];
  88.                 i++;
  89.             } else {
  90.                 // temp[i] > temp[j]
  91.                 nums[k] = temp[j];
  92.                 j++;
  93.             }
  94.         }
  95.     }
  96. }

4、快速排序

  1. import java.util.Random;
  2.  
  3. public class Solution {
  4.  
  5.     // 快速排序 2：双指针（指针对撞）快速排序
  6.  
  7.     /**
  8.      * 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序
  9.      */
  10.     private static final int INSERTION_SORT_THRESHOLD = 7;
  11.  
  12.     private static final Random RANDOM = new Random();
  13.  
  14.     public int[] sortArray(int[] nums) {
  15.         int len = nums.length;
  16.         quickSort(nums, 0, len - 1);
  17.         return nums;
  18.     }
  19.  
  20.     private void quickSort(int[] nums, int left, int right) {
  21.         // 小区间使用插入排序
  22.         if (right - left <= INSERTION_SORT_THRESHOLD) {
  23.             insertionSort(nums, left, right);
  24.             return;
  25.         }
  26.  
  27.         int pIndex = partition(nums, left, right);
  28.         quickSort(nums, left, pIndex - 1);
  29.         quickSort(nums, pIndex + 1, right);
  30.     }
  31.  
  32.     /**
  33.      * 对数组 nums 的子区间 [left, right] 使用插入排序
  34.      *
  35.      * @param nums  给定数组
  36.      * @param left  左边界，能取到
  37.      * @param right 右边界，能取到
  38.      */
  39.     private void insertionSort(int[] nums, int left, int right) {
  40.         for (int i = left + 1; i <= right; i++) {
  41.             int temp = nums[i];
  42.             int j = i;
  43.             while (j > left && nums[j - 1] > temp) {
  44.                 nums[j] = nums[j - 1];
  45.                 j--;
  46.             }
  47.             nums[j] = temp;
  48.         }
  49.     }
  50.  
  51.     private int partition(int[] nums, int left, int right) {
  52.         int randomIndex = left + RANDOM.nextInt(right - left + 1);
  53.         swap(nums, randomIndex, left);
  54.  
  55.         int pivot = nums[left];
  56.         int lt = left + 1;
  57.         int gt = right;
  58.  
  59.         // 循环不变量：
  60.         // all in [left + 1, lt) <= pivot
  61.         // all in (gt, right] >= pivot
  62.         while (true) {
  63.             while (lt <= right && nums[lt] < pivot) {
  64.                 lt++;
  65.             }
  66.  
  67.             while (gt > left && nums[gt] > pivot) {
  68.                 gt--;
  69.             }
  70.  
  71.             if (lt >= gt) {
  72.                 break;
  73.             }
  74.  
  75.             // 细节：相等的元素通过交换，等概率分到数组的两边
  76.             swap(nums, lt, gt);
  77.             lt++;
  78.             gt--;
  79.         }
  80.         swap(nums, left, gt);
  81.         return gt;
  82.     }
  83.  
  84.     private void swap(int[] nums, int index1, int index2) {
  85.         int temp = nums[index1];
  86.         nums[index1] = nums[index2];
  87.         nums[index2] = temp;
  88.     }
  89. }

5、堆排序 

  1. public class Solution {
  2.  
  3.     public int[] sortArray(int[] nums) {
  4.         int len = nums.length;
  5.         // 将数组整理成堆
  6.         heapify(nums);
  7.  
  8.         // 循环不变量：区间 [0, i] 堆有序
  9.         for (int i = len - 1; i >= 1; ) {
  10.             // 把堆顶元素（当前最大）交换到数组末尾
  11.             swap(nums, 0, i);
  12.             // 逐步减少堆有序的部分
  13.             i--;
  14.             // 下标 0 位置下沉操作，使得区间 [0, i] 堆有序
  15.             siftDown(nums, 0, i);
  16.         }
  17.         return nums;
  18.     }
  19.  
  20.     /**
  21.      * 将数组整理成堆（堆有序）
  22.      *
  23.      * @param nums
  24.      */
  25.     private void heapify(int[] nums) {
  26.         int len = nums.length;
  27.         // 只需要从 i = (len - 1) / 2 这个位置开始逐层下移
  28.         for (int i = (len - 1) / 2; i >= 0; i--) {
  29.             siftDown(nums, i, len - 1);
  30.         }
  31.     }
  32.  
  33.     /**
  34.      * @param nums
  35.      * @param k    当前下沉元素的下标
  36.      * @param end  [0, end] 是 nums 的有效部分
  37.      */
  38.     private void siftDown(int[] nums, int k, int end) {
  39.         while (2 * k + 1 <= end) {
  40.             int j = 2 * k + 1;
  41.             if (j + 1 <= end && nums[j + 1] > nums[j]) {
  42.                 j++;
  43.             }
  44.             if (nums[j] > nums[k]) {
  45.                 swap(nums, j, k);
  46.             } else {
  47.                 break;
  48.             }
  49.             k = j;
  50.         }
  51.     }
  52.  
  53.     private void swap(int[] nums, int index1, int index2) {
  54.         int temp = nums[index1];
  55.         nums[index1] = nums[index2];
  56.         nums[index2] = temp;
  57.     }
  58. }
  59.

6、希尔排序

  1. public class Solution {
  2.  
  3.     // 希尔排序
  4.  
  5.     public int[] sortArray(int[] nums) {
  6.         int len = nums.length;
  7.         int h = 1;
  8.  
  9.         // 使用 Knuth 增量序列
  10.         // 找增量的最大值
  11.         while (3 * h + 1 < len) {
  12.             h = 3 * h + 1;
  13.         }
  14.  
  15.         while (h >= 1) {
  16.             // insertion sort
  17.             for (int i = h; i < len; i++) {
  18.                 insertionForDelta(nums, h, i);
  19.             }
  20.             h = h / 3;
  21.         }
  22.         return nums;
  23.     }
  24.  
  25.     /**
  26.      * 将 nums[i] 插入到对应分组的正确位置上，其实就是将原来 1 的部分改成 gap
  27.      *
  28.      * @param nums
  29.      * @param gap
  30.      * @param i
  31.      */
  32.     private void insertionForDelta(int[] nums, int gap, int i) {
  33.         int temp = nums[i];
  34.         int j = i;
  35.         // 注意：这里 j >= deta 的原因
  36.         while (j >= gap && nums[j - gap] > temp) {
  37.             nums[j] = nums[j - gap];
  38.             j -= gap;
  39.         }
  40.         nums[j] = temp;
  41.     }
  42. }
  43.

7、冒泡排序

  1. public class Solution {
  2.  
  3.     // 冒泡排序：超时
  4.  
  5.     public int[] sortArray(int[] nums) {
  6.         int len = nums.length;
  7.         for (int i = len - 1; i >= 0; i--) {
  8.             // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，
  9.             // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
  10.             boolean sorted = true;
  11.             for (int j = 0; j < i; j++) {
  12.                 if (nums[j] > nums[j + 1]) {
  13.                     swap(nums, j, j + 1);
  14.                     sorted = false;
  15.                 }
  16.             }
  17.             if (sorted) {
  18.                 break;
  19.             }
  20.         }
  21.         return nums;
  22.     }
  23.  
  24.     private void swap(int[] nums, int index1, int index2) {
  25.         int temp = nums[index1];
  26.         nums[index1] = nums[index2];
  27.         nums[index2] = temp;
  28.     }
  29. }
  30.

8、折半排序

  1. public class BinaryInsertSortTest {
  2. 	public void binaryInsertSort(int[] data) {
  3. 		for (int i = 1; i < data.length; i++) {
  4. 			if (data[i] < data[i - 1]) {
  5. 				// 缓存i处的元素值
  6. 				int tmp = data[i];
  7. 				// 记录搜索范围的左边界
  8. 				int low = 0;
  9. 				// 记录搜索范围的右边界
  10. 				int high = i - 1;
  11. 				while (low <= high) {
  12. 					// 记录中间位置
  13. 					int mid = (low + high) / 2;
  14. 					// 比较中间位置数据和i处数据大小，以缩小搜索范围
  15. 					if (data[mid] < tmp) {
  16. 						low = mid + 1;
  17. 					} else {
  18. 						high = mid - 1;
  19. 					}
  20. 				}
  21. 				//将low~i处数据整体向后移动1位
  22. 				for (int j = i; j > low; j--) {
  23. 					data[j] = data[j - 1];
  24. 				}
  25. 				data[low] = tmp;
  26. 			}
  27. 		}
  28. 	}

题目链接：力扣 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/735816
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号