排序的基本概念
插入排序
直接插入排序
- 从空间分析：空间复杂度 o （1），只要一个元素的辅助空间用于位置的交换，也称原地排序算法。
- 从时间分析：时间复杂度 o（n^2），对随机顺序的数据来说，移动和比较的次数接近最坏情况。
- 由于直接插入算法的元素移动是顺序的，该排序算法是稳定的
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
if (j == 0) {
arr[0] = temp;
}
} else {
arr[j + 1] = temp;
break;
}
}
}
折半插入排序
前提条件：有序
- 过程：利用二分查找法来确定要插入的位置，将该位置及以后的位置依次向后移动一位，然后将要插入的数插入该位置
public void binaryInsertionSort(int[] arr, int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i];
int left = 0, right = i - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > temp) {
right = mid - 1;
} else if (arr[mid] < temp) {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
}
希尔排序
- 会跳着排，不稳定、时间复杂度在 nlogn 和 n^2 之间，所以定位很尴尬，算法本身比较复杂，但在 nlogn级别 时间复杂度大行其道的高级排序算法根本没存在的意义。。。不做过深研究
交换排序
冒泡排序
- 只进行元素间的顺序移动，所以是一个稳定的排序算法
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
快速排序
快速排序是名副其实的，因为在实际应用中，它几乎是最快的排序算法，被评为20世纪十大算法之一。
快排在实践中有两种常用的分割策略：
- 第一种分割策略
- 首先用变量备份轴元素
- 取两个指针 left 和 right，它们的初始值分别指向序列最左边的下标，序列最右边的下标。当left 小于 right时
- 从right所指的位置向左搜索，找到第一个小于等于轴的元素，把这个元素移动到left的位置，再从left所指的位置开始向右搜索，找到第一个大于轴的元素，把它移动到right所指的位置。
- 重复这个过程，直到left等于right，最后把轴元素放在left所指的位置。
public int partition1(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] > pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
- 第二种分割策略
- 首先用变量备份轴元素
- 取两个指针 left 和 right，它们的初始值分别指向序列左边第二个元素下标，序列最右边的下标。当left不大于right时
- 向右移动left，使其停在第一个大于轴元素的元素位置，同时向左移动right，使其停在第一个不大于轴元素的位置，然后交换left和right位置的元素，然后继续移动left、right，交换相应的元素
- 重复这个过程，直至left大于right。
public int partition2(int[] arr, int start, int end) {
int pivot = arr[start];
int left = start, right = end;
while (left <= right) {
while (left <= right && arr[left] <= pivot)
left++;
while (left <= right && arr[right] > pivot)
right--;
if (left < right) {
swap(arr[left], arr[right]);
left++;
right--;
}
swap(arr[start], arr[right]);
return right;
}
}
快排就是递归调用上述分割策略来不断划分子序列从而完成排序
public void quickSort(int[] arr, int left, int right) {
int p = partition1(arr, left, right);
quickSort(arr, left, p - 1);
quickSort(arr, p + 1, right);
}
快排空间的开销主要是递归调用时所使用的栈，因此快排空间开销和递归调用的栈的深度成正比，故最好的空间复杂度为 logn，最坏的空间复杂度为 n
选择排序
简单选择排序
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
