排序之——直接插入排序
适用场景——短数组或大部分有序情况,最好情况下可以达到O(N)的复杂度。
时间复杂度:O(N^2)
代码如下:
public static int[] sortArray(int[] nums) {
int len = nums.length;
// 循环不变量:将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for (int i = 1; i < len; i++) {
// 先暂存这个元素
int temp = nums[j];
int j = i;
// 注意边界 j > 0
//将前面大的值往后挪
while (j > 0 && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
return nums;
}
排序之——归并排序(有优化)
基本思路:借助额外空间,合并两个有序数组,得到更长的有序数组。
//归并排序
public class Main {
//当列表长度小于等于7时,定义为短数组,采用插入排序
private static final int INSERTION_SORT_THRESHOLD = 7;
public static int[] sortArray(int[] nums) {
int len = nums.length;
int[] temp = new int[len];
mergeSort(nums, 0, len - 1, temp);
return nums;
}
private static void mergeSort(int[] nums, int left, int right, int[] temp) {
// 小区间使用插入排序(优化一)
if (right - left <= INSERTION_SORT_THRESHOLD) {
insertionSort(nums, left, right);
return;
}
int mid = (left + right) >> 1;
//int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, temp); //[left,mid]
mergeSort(nums, mid + 1, right, temp); //[mid + 1,right]
// 如果数组的这个子区间本身有序,无需合并(优化二)
if (nums[mid] <= nums[mid + 1]) {
return;
}
mergeOfTwoSortedArray(nums, left, mid, right, temp);
}
private static void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
// Object src : 原数组 ——nums
// int srcPos : 从元数据的起始位置开始 ——left
// Object dest : 目标数组 ——temp
// int destPos : 目标数组的开始起始位置 ——left
// int length : 要copy的数组的长度 ——right - left + 1
//复制数组
System.arraycopy(nums,left,temp,left,right - left + 1);
int i = left;
int j = mid + 1;
for (int k = left;k<=right;k++){
if (i == mid + 1){//[left,mid]有序数组遍历完
nums[k] = temp[j];
j++;
}
else if (j == right + 1){//[mid + 1,right]有序数组遍历完
nums[k] = temp[i];
i++;
}
else if (temp[i] <= temp[j]){//前一个数组索引位置小
nums[k] = temp[i];
i++;
}
else{
//temp[i] > temp[j]
nums[k] = temp[j];
j++;
}
}
}
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int j = i;
int temp = arr[j];
while (j > left && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
}
排序之——快速排序(已优化)
基本思路:快速排序每一次都排定一个元素(这个元素呆在了它最终应该呆的位置),然后递归地去排它左边的部分和右边的部分,依次进行下去,直到数组有序;
算法思想:分而治之(分治思想),与「归并排序」不同,「快速排序」在「分」这件事情上不像「归并排序」无脑地一分为二,而是采用了 partition 的方法,因此就没有「合」的过程。
实现细节(注意事项):(针对特殊测试用例:顺序数组或者逆序数组)一定要随机化选择切分元素(pivot),否则在输入数组是有序数组或者是逆序数组的时候,快速排序会变得非常慢(等同于冒泡排序或者「选择排序」);
import java.util.Random;
//快速排序
public class Main {
//当列表长度小于等于7时,定义为短数组,采用插入排序
private static final int INSERTION_SORT_THRESHOLD = 7;
private static final Random RANDOM = new Random();
public static int[] sortArray(int[] nums) {
int len = nums.length;
quickSort(nums, 0, len - 1);
return nums;
}
private static void quickSort(int[] nums, int left, int right) {
// 小区间使用插入排序
if (right - left <= INSERTION_SORT_THRESHOLD) {
insertionSort(nums, left, right);
return;
}
int pIndex = partition(nums, left, right);//这个元素呆在了它最终应该呆的位置
quickSort(nums, left, pIndex - 1); //递归左边部分
quickSort(nums, pIndex + 1, right);//递归右边部分
}
private static int partition(int[] nums, int left, int right) {
int randomIndex = RANDOM.nextInt(right - left + 1) + left;
swap(nums, left, randomIndex);
// 基准值
int pivot = nums[left];
int lt = left;
// 循环不变量:
// all in [left + 1, lt] < pivot
// all in [lt + 1, right) >= pivot
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
lt++;
swap(nums, i, lt);
}
}
swap(nums, left, lt);
return lt;
}
//交换函数
private static void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
private static void insertionSort(int[] nums, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int j = i;
int temp = nums[j];
while (j > left && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
}
}



