排序算法（二）

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);}