一般的なソートアルゴリズムのまとめ

宣言

文章はすべて本人の技術ノートで、転載は出典を明記してください:[1]https://segmentfault.com/u/yzwall [2] blog.csdn.net/j_dark/

ソートの説明

並べ替えアルゴリズムデフォルト昇順並べ替え

試験問題lintcode Sort Integersとlintcode Sort Integers II(要求$O(ntimeslog n)$時間複雑度)

コードの簡潔化のため、交換方法swap:

が提供される.

    private void swap(int[] A, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = A[index1];
        A[index1] = A[index2];
        A[index2] = temp;
    }

1ソートの選択

「選択」:ソートの実現方法を選択するのが最も簡単で、ソートごとに$A[i]~A[A.length-1]$の最小値$A[minIndex]$と$A[i]$を位置を交換し、選択(最小値)は入力に関係なく、効率が最も遅い.

/**
 *  （ ）
 *  O(n^2)， O(1)
 * @author yzwall
 */
class Solution {
    public void sortIntegers(int[] A) {
        for (int i = 0; i < A.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < A.length; j++) {
                minIndex = A[minIndex] > A[j] ? j : minIndex;
            }
            swap(A, i, minIndex);
        }
    }
}

2バブルソート

「バブル」:バブルが発生するたびに最大値(昇順)を現在のソート配列区間の最後の位置、すなわち右にバブルが発生するため、$A[j-1]$は常にバブル区間の極大値を維持する.

/**
 *  （ ）
 *  O(n^2)， O(1)
 * @author yzwall
 */
class Solution {
    public void sortIntegers(int[] A) {
        // i A[i - 1]
        for (int i = A.length; i > 0; i--) {
            //  A[0]~A[i - 1]， （ ）
            for (int j = 1; j < i; j++) {
                if (A[j - 1] > A[j]) {
                    swap(A, j, j - 1);
                }
            }
            //  ，A[i - 1] A[0] ~ A[i - 1] 
        }
    }
}

3直接挿入ソート

「挿入」:ソートされる要素を左側の整列(昇順)列に挿入するたびに、左に挿入されます.$A[j]$はシーケンス内の挿入要素の位置を常に維持します.

/**
 *  （ ）
 *  O(n^2)， O(1)
 * @author yzwall
 */
class Solution {
    public void sortIntegers(int[] A) {
        //  A[i]~A[A.length - 1] 
        for (int i = 1; i < A.length; i++) {
            for (int j = i; j > 0; j--) {
                if (A[j] < A[j - 1]) {
                    swap(A, j, j - 1);
                }
            }
        }
    }
}

4ヒルソート

補足する必要があります.

4集計ソート

小結リンクの並べ替え

/**
 * http://www.lintcode.com/en/problem/sort-integers-ii/
 *  （ ）
 * @author yzwall
 */
class Solution {
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        
        mergeSort(A, 0, A.length - 1);
    }
    
    public void mergeSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);
        merge(A, start, end);
    }
    
    private void merge(int[] A, int start, int end) {
        int mid = start + (end - start) / 2;
        int i = start, j = mid + 1, index = 0;
        int[] temp = new int[end - start + 1];
        while (i <= mid && j <= end) {
            if (A[i] < A[j]) {
                temp[index++] = A[i++];
            } else {
                temp[index++] = A[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = A[i++];
        } 
        while (j <= end) {
            temp[index++] = A[j++];
        }
        for (int k = 0; k < index; k++) {
            A[start + k] = temp[k];
        }
    }
}

5クイックソート

クイックソートリンク

/**
 * http://www.lintcode.com/en/problem/sort-integers-ii/
 *  （ ）
 * @author yzwall
 */
class Solution {
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        
        quickSort(A, 0, A.length - 1);
    }
    
    public void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = A[start + (end - start) / 2];
        int left = start, right = end;
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left++;
            }
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

6ヒープソート

スタック実装リンク

6バレルソート

補足する必要があります.

7カウントソート

補足する必要があります.