1、稳定性:排序之后,原先相等的两个数的先后顺序不发生变化
插入排序1、直接插入排序O(n^2)稳定
最好时间复杂度O(n):数组已经有序,内层循环一次都不走
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// for (int j = i; j >= 1; j--) {
// if (arr[j] < arr[j - 1]) {
// break;
// }else {
// swap(arr,j,j-1);
// }
// }
for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
}
优化:折半插入排序
public static void insertionSortBS(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int val = arr[i];
//有序区间[left,right)左闭右开
int left = 0;
int right = i;
while (left < right) {
int mid = (left + right) / 2;
if (val < arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
//搬移【left,i)的元素
for (int j = i; j > left; j--) {
arr[j] = arr[j - 1];
}
arr[left] = val;
}
}
2、希尔排序O(n^1.2 ~ n^1.3)
【希尔排序就是对插入排序的优化,又称为缩小增量排序】
【不断将小数组调整的近乎有序 ,整个大数组就接近有序状态 ,这个时候使用插入排序效率很高】
【核心思想:当数组近乎有序,插入排序效率很高】
【思路:①先选定一个整数gap。将待排序的数据分为gap组,所有距离为gap的为同一组,对每一个小数组进行插入 排序②step.gap = gap /2或者3,重复①,当gap==1,此时整个数组已经调整近乎有序,此时的对数组进行一次插入排序 即可。】
public static void shellSort(int[] arr) {
int gap = arr.length >> 1;
//预处理阶段
// while (gap >1 ){
// insertionGap(arr,gap);
// gap =gap>>1;
// }
// insertionSort(arr);
while (gap >= 1) {
insertionGap(arr, gap);
gap = gap >> 1;
}
}
private static void insertionGap(int[] arr, int gap) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= gap && arr[j] < arr[j - gap]; j--) {
swap(arr, j, j - gap);
}
}
}
选择排序
1、直接选择排序O(n^2)
直接从无序区间中选择一个最大 或者最小的元素,放在无序区间的最后或者最前,直到数组排序完成。
public static void selectionSort(int[] arr) {
//有序区间[0,i]
//无序区间[i+1,arr.length]
for (int i = 0; i < arr.length-1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min =j;
}
}
swap(arr,i,min);//把最小值放在无序区间之前
}
}
优化:双向选择排序,每次从无序区间中选最小值和最大值,存放在无序区间的最开始和最后面位置,重复上述过程
public static void selectionSortOP(int[] arr) {
int low = 0;
int higt = arr.length - 1;
while (low < higt) {
int min = low;
int max = low;
for (int i = low + 1; i <= higt; i++) {
if (arr[i] < arr[min]) {
min = i;
}
if (arr[i] > arr[max]) {
max = i;
}
}
//min对应最小值索引
swap(arr, min, low);
if (max == low) {
max = min;
}
swap(arr, max, higt);
low++;
higt--;
}
}
2、堆排序O(nlogn)
1、任意数组可以看作完全二叉树,将其调整为最大堆。(heapify操作)
2、不断交换堆顶元素和最后一个元素的位置,进行siftDown操作。
public static void heapSort(int[] arr) {
//1、将任意数组进行heapify操作调整为最大堆
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
//2、不断交换堆顶元素和数组末尾,每进行一次交换就进行siftDowm操作,就有一个元素落在了最终位置
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
siftDown(arr, 0, i);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void siftDown(int[] arr, int i, int length) {
while (i * 2 + 1 < length) {
int j = i * 2 + 1;
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (arr[i] <= arr[j]) {
swap(arr, i, j);
i = j;//继续下沉
} else {
break;
}
}
}
交换排序
1、冒泡排序O(n^2)稳定
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSort = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j,j+1);
isSort = true;
}
}
if (!isSort) {//已经有序
break;
}
}
}
2、快速排序 O(nlogn)
归并排序O(nlogn)稳定【归:不断将原数组拆分为子数组(一分为二)直到 每个子数组只剩下一个元素,归结束】
【并:不断合并相邻的两个子数组为一个大数组,合并的过程就是将两个已经有序的子数组合并为一个大的有序子数组,直到合并到整个数组】
【核心操作:1、先将两个 子数组所有内容复制到 新数组 2、遍历两个子数组将较小值写回原数组】
【优化点:①小数组使用插入排序②若整个数组已经有序不需要合并】
public static void mergeSort(int[] arr) {
mergeSortInternal(arr, 0, arr.length - 1);
}
private static void mergeSortInternal(int[] arr, int l, int r) {
//小数组直接插入排序
// if (l >= r) {
// return;
// }
if (r - l <= 15) {
insertionSort(arr, l, r);
return;
}
// int mid = (l+r)>>1;
int mid = l + ((r - l) >> 1);//降低越界可能性
mergeSortInternal(arr, l, mid);
mergeSortInternal(arr, mid + 1, r);
//两个 子数组已经有序,合并即可。
//若整个数组有序不需要合并
if (arr[mid] > arr[mid + 1]) {
merge(arr, l, mid, r);
}
}
private static void insertionSort(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
for (int j = i; j >= l + 1 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] aux = new int[r - l + 1];
for (int i = 0; i < aux.length; i++) {
aux[i] = arr[l + i];
}
int i = l;//第一个数组开始下标
int j = mid + 1;//第二个数组开始下标
for (int k = l; k <= r; k++) {
if (i > mid) {
//第一个数组遍历完成
arr[k] = aux[j - l];
j++;
} else if (j > r) {
//第二个数组遍历完成
arr[k] = aux[i - l];
i++;
} else if (aux[i - l] < aux[j - l]) {
//将aux[i-l]写回arr[k]
arr[k] = aux[i - l];
i++;
} else {
//aux[i-l]>aux[j-l]写回aux[j-l]
arr[k] = aux[j - l];
j++;
}
}
}
外部排序
1、桶排序O(n)
2、基数排序O(n)
3、技术排序O(n)



