基礎的排序算法

標簽：頻繁   最大的   array   --   簡單   序列   兩個指針   算法   元素   

簡單梳理一下以前學過的排序算法

冒泡排序

平均時間復雜度：O(n2)；穩定

1. 比較相鄰元素，如果前面的比后面大，就交換兩個元素
2. 每一對相鄰元素做同樣的比較，從開始第一對元素一直比到結尾，一輪結束最后的元素是最大的。
3. 除了每輪比較出來的最大元素，對其他元素重復以上操作。

	public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

選擇排序

平均時間復雜度：O(n2)；不穩定

1. 在所有元素中選取最小的元素，放在第一個位置。
2. 在剩余元素里選取最小的元素，放在第二個位置。
3. 以此類推

	public void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }

插入排序

平均時間復雜度：O(n2)；穩定

1. 以第一個元素為有序序列，從末尾開始比較，即要插入的元素和已經有序的最大者開始比起。
2. 如果比它大則插入后面，否則一直比較，直到找到它該插入的位置。
3. 如果遇到的元素和要插入的元素相等，那么要插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，所以插入排序是穩定的。

	public void insertionSort(int[] array) {
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]){
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
    }

希爾排序

平均時間復雜度：O(nlog?n)；不穩定

希爾排序又叫做最小增量排序，將整個待排序的序列分割成為若干子序列，分別進行插入排序。

1. 選擇增量 gap=length/2，這種增量選擇可以用一個序列來表示，{n/2, (n/2)/2, ... 1}，稱為增量序列。
2. 對每個子序列進行插入排序后，縮小增量繼續以 gap = gap/2 的方式執行。

	public void shellSort(int[] array){
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }

歸并排序

分治法的典型應用。始終都是 O(nlogn) 的時間復雜度，代價是需要額外的內存空間。

平均時間復雜度：O(nlogn)；穩定

1. 將長度為 n 的序列分成兩個長度為 n/2 的子序列；
2. 分別對子序列采用歸并排序；
3. 將兩個排序好的子序列合并成一個有序序列；

 	public void sort(int[] array) {
        //在排序前，先建好一個長度等于原數組長度的臨時數組，避免遞歸中頻繁開辟空間
        int[] temp = new int[array.length];
        sort(array, 0, array.length - 1, temp);
    }

    public void sort(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(array, left, mid, temp);	//左邊歸并排序，使得左子序列有序
            sort(array, mid + 1, right, temp);//右邊歸并排序，使得右子序列有序
            merge(array, left, mid, right, temp);//將兩個有序子數組合并操作
        }
    }

	public void merge(int[] array, int left, int mid, int right, int[] temp){
        int i = left;	//左序列指針
        int j = mid + 1;	//右序列指針
        int t = 0;	//臨時數組指針
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[t++] = array[i++];
            } else {
                temp[t++] = array[j++];
            }
        }
        while (i <= mid) {//將左邊剩余元素填充進temp中
            temp[t++] = array[i++];
        }
        while (j <= right) {//將右序列剩余元素填充進temp中
            temp[t++] = array[j++];
        }
        t = 0;
        //將temp中的元素全部拷貝到原數組中
        while (left <= right) {
            array[left++] = temp[t++];
        }
    }

快速排序

平均時間復雜度：O(nlogn)；不穩定

1. 在序列中選一個基準數（pivot），一般選首位置元素為基準。
2. 快排利用兩個指針，分別設為左left，右right，雙向進行。比基準數大的放右邊，比基準數小的放左邊，當left < right 時，遍歷結束。
3. 利用遞歸，把比基準小的子序列、比基準大的子序列分別重復上述排序步驟。

    public void quickSort(int[] array, int left, int right) {
        if (left < right) {
            int index = getIndex(array, left, right);
            quickSort(array, left, index - 1);
            quickSort(array, index + 1, right);
        }
    }

    public int getIndex(int[] array, int left, int right) {

        int pivot = array[left];
        
        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[right] = pivot;
        return right;
    }

    public void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

堆排序

有點遺忘，回頭補上

基礎的排序算法

標簽：頻繁   最大的   array   --   簡單   序列   兩個指針   算法   元素   

原文地址：https://www.cnblogs.com/leejk/p/15068383.html