常用排序算法(希尔,归并,快排)

4. 希尔排序

• 时间复杂度 : O(n^1.3) ~ O(n^1.5)
• 空间复杂度 : O(1)
• 稳定性 : 不稳定(因为在交换的过程中,有跳跃交换,所以不稳定)
• 算法思想 :希尔排序是插入排序的优化版本,由于简单插入排序的只能交换相邻元素,所以每次只能将逆序对数减1,它通过交换不相邻的元素, 使得每次将逆序对数量减小大于1.
  首先将数组元素按照h=4间距分为数对,然后在这些数对之间进行一次插入排序,然后h/2为间距进行插入排序,最后h=1,也就是相邻之间元素进行插入排序;

 public static <T extends Comparable<T>> void shellSort(T[] arr) {
		int n = arr.length; 
		int h = 1 ; 
		while(h <n/3 ){
		h = h *3 +1 ; // 按照3*n+1增加间距
		}
	while(h >= 1){
		for(int i=h;i<n;i++){
			for(int j = i ; j>h&&arr[j].compareTo(arr[j-h]);j-=h)
			{
			swap(arr,j,j-h);
			}		
		}
		h = h/3; 
	}
}

5. 归并排序

• 时间复杂度 : O(nlogn) 划分过程类似二分(logn) 归并过程需要将数组都遍历一遍(O(n))
• 空间复杂度: 使用了辅助数组> O(n)
• 稳定性: 稳定
• 算法思想 : 基于分治的思想,首先先将数组不断划分,划分规模至两个相邻元素,然后进行归并,合并两个有序数组,刚开始是相邻元素之间合并,再往后,规模不断扩大,实现全数组的合并

public class 归并排序 {

    public static void mergeSort(int[] arr, int low, int high, int[] temp) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid, temp);    //对左边序列进行归并
            mergeSort(arr, mid + 1, high, temp);// 对右边序列进行归并
            merge(arr, low, mid, high, temp); //对两个有序序列进行合并
        }
    }

    /**
     * 对两个有序序列进行合并
     *
     * @param arr
     * @param low
     * @param mid
     * @param high
     * @param temp
     */
    private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
        int i = 0; // 辅助数组temp的下标值
        int j = low; // 左边的起始索引
        int k = mid + 1;// 右边的起始索引
        while (j <= mid && k <= high) {  //此处就是合并两个有序数组[由小到大
            if (arr[j] < arr[k]) {
                temp[i++] = arr[j++];
            } else {
                temp[i++] = arr[k++];
            }
        }
        //将剩余的数拷贝置temp
        while (j <= mid) {
            temp[i++] = arr[j++];
        }
        while (k <= high) {
            temp[i++] = arr[k++];
        }
        //将temp中数据拷贝置arr,因为是局部的数据,所以arr[low+n]要根据low的位置来定位
        for (int n = 0; n < i; n++) {
            arr[low + n] = temp[n];
        }
    }
    public static void main(String[] args) {
        int[] arr = {11, 44, 23, 67, 88, 65, 34, 48, 9, 12};
        int[] tmp = new int[arr.length];    //新建一个临时数组存放
        mergeSort(arr, 0, arr.length - 1, tmp);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

6. 快速排序

• 时间复杂度 : 加入每4次正好将数组对半分,这种情况下递归调用次数才是最小的,最好情况为 : O(nlogn),而如果每次切分第一次从最小的元素切分,第二次从第二小元素切分,此时最坏情况: O(n^2)
• 空间复杂度: 因为没有开辟辅助数组 O(1)
• 算法思想 : 基于分治的思想,将数组不 断的向小规模划分,每次向小规模划分的过程中会有一个partition的过程,在这个过程中会取第一个元素为切分元素,不断的从两头向中间遍历,从头遍历时如果遇到比自己小的元素,就将它放到切分元素的位置,从后往前遍历时,如果遇到比自己小的元素,就将其方放到从前往后遍历的最小元素的位置,每次partition,都能将数组中的元素根据切分元素分离开来,小于切分元素的在数组的前面,大于切分元素的在数组的后面.

 
    public static void QuickSort(int[] arr, int l, int h) {
        if (h <= l) {
            return;
        }
        int m = partition(arr, l, h);
        QuickSort(arr, l, m-1);
        QuickSort(arr, m + 1, h);


    }

    private static int partition(int[] arr, int l, int h) {

        int i = l;
        int j = h + 1;
        int v = arr[l];   //

        while (true) {
            while (v > arr[i++] && i != h) {
            } //从头开始如果当前切分元素大于arr[i] ;
            while (v < arr[--j] && j != l) {
            } // 从尾部开始遍历如果当前切分元素小于arr[j]
            if (i >= j)
                break;
            swap(arr, i, j);
        }
        swap(arr,l,j);
        return j;
    }

    private static void  swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }