1.希尔排序-Shell Sort
1.算法原理
将未排序序列按照增量gap的不同分割为若干个子序列，然后分别进行插入排序，得到若干组排好序的序列；
缩小增量gap，并对分割为的子序列进行插入排序；最后一次的gap=1，即整个序列，但此时已经基本有序，对整个序列使用插入排序，得到最终排好序的序列
公式表示：gap={n/2，(n/2)/2，...，1} = {t1，t2，...，tk}
即一共排序k次，增量gap称作希尔增量
算法图解可以参考以下两种：
2.算法复杂度
时间复杂度：最优复杂度：O(nlogn)；最差复杂度：O(n2)；平均复杂度：O(nlogn)
空间复杂度：O(1)
3.算法实现-Java
public int[] shellSort(int[] arr){
int len = arr.length;
int gap = len / 2;
while(gap > 0){
for(int i = gap; i < len; i++){
int currentValue = arr[i];
int preIndex = i - gap;
while(preIndex >= 0 && arr[preIndex] > currentValue){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = currentValue;
}
gap = gap / 2;
}
return arr;
}
2.归并排序-Merge Sort
1.算法原理
将未排序序列的所有元素分为若干组，每个元素为一组；将每组元素进行两两合并，合并时按照从小到大（或者从大到小）对元素进行排序，排序时比较每一组元素的头部即可；重复此步骤，直到最终只剩下一组数据，则排序完成
2.算法复杂度
时间复杂度：最优复杂度：O(nlogn)；最差复杂度：O(nlogn)；平均复杂度：O(nlogn)
空间复杂度：O(1)
3.算法实现-Java
public class MergeSort {
public static void main(String[] args) {
int[] a = {9, 6, 2, 3, 7, 4, 8, 5，1，0};
int L = 0;
int R = a.length - 1;
mergSort(a, L, R);
System.out.println(Arrays.toString(a));
}
static void mergSort(int[] arr, int L, int R) {
//只有一个数，直接返回
if (L == R) {
return;
} else {
int M = (L + R) / 2;
mergSort(arr, L, M);
mergSort(arr, M + 1, R);
merge(arr, L, M + 1, R);
}
}
static void merge(int[] arr, int L, int M, int R) {
int left_size = M - L;
int right_size = R - M + 1;
int[] L_arr = new int[left_size];
int[] R_arr = new int[right_size];
// 1 填充左边的数组
for (int i = L; i < M; i++) {
L_arr[i - L] = arr[i];
}
// 2 填充右边的数组
for (int i = M; i <= R; i++) {
R_arr[i - M] = arr[i];
}
// 3 合并
int i = 0, j = 0, k = L;
while (i < left_size && j < right_size) {
if (L_arr[i] > R_arr[j]) {
arr[k] = R_arr[j];
k++;
j++;
} else {
arr[k] = L_arr[i];
i++;
k++;
}
}
// 4 若右边数组已空,把剩余左边数组补上
while (i < left_size) {
arr[k] = L_arr[i];
i++;
k++;
}
// 5 若左边数组已空,同上
while (j < right_size) {
arr[k] = R_arr[j];
k++;
j++;
}
}
}
3.快速排序-Quick Sort
1.算法原理
在未排序的序列中选择一个数作为基准（一般选择序列的第一个数），序列的最左侧和最右侧设置两个指针L和R；
其中L从左往右移动，R从右往左移动；
首先R从右向左移动一位，若指向的元素小于（大于）基准，则将其移动到序列的最左边（最右边），然后L从左向右移动一位，指向的元素与基准比较后，执行相同操作；
直到L与R移动到同一位置，说明第一次排序完成，此时相遇的位置就是基准元素的位置；
接下来，在基准的左右两边序列各选一个基准，执行上述操作，直到排序完成
2.算法复杂度
时间复杂度：最优复杂度：O(nlogn)；最差复杂度：O(nlogn)；平均复杂度：O(nlogn)
空间复杂度：O(1)
3.算法实现-Java
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low > high){
return;
}
i = low;
j = high;
//temp为基准元素
temp = arr[low];
while (i < j) {
//右边，依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
//左边，依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
//如果满足条件则交换
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
