排序算法笔记

1. 插入排序

从前往后遍历，把遍历到的数字插入到前面排好序部分的合适位置。

import java.util.Scanner;

public class InsertionSort {

    public static void main(String[] args) {
        int N, i, j;
        int[] A = new int[100];

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        for(i = 0; i<N; i++){
            A[i] = in.nextInt();
        }
        printArr(A, N);
        insertSort(A, N);
    }

    static void printArr(int A[], int N){
        int i;
        for(i=0; i<N; i++){
            if(i>0) System.out.print(" ");
            System.out.print(A[i]);
        }
        System.out.println("");
    }

    static void insertSort(int A[], int N){
        int j,v;
        for(int i=1; i<N; i++){
            v=A[i];
            j=i-1;
            while(j>=0 && A[j]>v){
                //依次向后移
                A[j+1] = A[j];
                j--;
            }
            A[j+1] = v;
            printArr(A, N);
        }
    }
}

2. 冒泡排序

从前往后遍历，把遍历到的数字和后面数字做交换。

public class BubbleSort {

    public static void main(String[] args) {
        int[] A = {5,3,2,4,1};
        int n = 5;
        System.out.println(bubbleSort(A, n));
        for (int i : A) {
            System.out.print(i+" ");
        }
    }

    static int bubbleSort(int A[], int n){
        int sw = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n-i-1; j++){
                if(A[j]>=A[j+1]){
                    int temp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = temp;
                    sw++;
                }
            }
        }
        return sw;
    }
}

3. 选择排序

从前往后遍历，把最小的值与前面未排序的部分交换。

public class SelectionSort {

    public static void main(String[] args) {
        int[] A = {32, 13, 13, 1,223,6};
        int n = 6;
        System.out.println(selectionSort(A, n));
        for (int i : A) {
            System.out.print(i+" ");
        }
    }

    static int selectionSort(int A[], int n){
        int sw = 0;
        int j,minj;
        for(int i=0; i<n; i++){
            minj = i;
            for(j=i; j<n; j++){
                if(A[minj]>A[j]){
                    minj = j;
                }
            }
            int temp = A[i];
            A[i] = A[minj];
            A[minj] = temp;
            if(i!=minj){
                sw++;
            }
        }
        return sw;
    }
}

4. 稳定排序

能时常保证稳定输出的算法成为稳定排序算法。

排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

package 初等排序;

public class StableSort {

    public static void main(String[] args) {
        Card[] c1 = {new Card('H','4'),
                new Card('C','9'),
                new Card('S','4'),
                new Card('D','2'),
                new Card('C','3')
        };
        Card[] c2 = {new Card('H','4'),
                new Card('C',
                        '9'),
                new Card('S','4'),
                new Card('D','2'),
                new Card('C','3')
        };
        bubbleSort(c1, 5);
        selectionSort(c2, 5);
        for (Card card : c1) {
            System.out.println(card);
        }
        System.out.println("-------------------");
        for (Card card : c2) {
            System.out.println(card);
        }
        System.out.println(isStable(c1, c2,5));
    }

    static void bubbleSort(Card[] c, int n){
        for(int i=0; i<n; i++){
            for(int j=0; j<n-i-1; j++){
                if(c[j].value > c[j+1].value){
                    Card temp = c[j];
                    c[j] = c[j+1];
                    c[j+1] = temp;
                }
            }
        }
    }

    static void selectionSort(Card[] c, int n){
        for(int i=0; i<n; i++){
            int minj = i;
            for(int j=i; j<n; j++){
                if(c[minj].value>c[j].value){
                    minj = j;
                }
            }
            if(i!=minj) {
                Card temp = c[minj];
                c[minj] = c[i];
                c[i] = temp;
            }
        }
    }

    static boolean isStable(Card[] c1, Card[] c2, int n){
        for(int i=0; i<n; i++){
            if(c1[i].suit != c2[i].suit){
                return false;
            }
        }
        return true;
    }
}

class Card {
    char suit;
    char value;

    public Card(char suit, char value) {
        this.suit = suit;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Card{" +
                "suit=" + suit +
                ", value=" + value +
                '}';
    }
}

5. 希尔排序

分组之后，进行插入排序

package 初等排序;

public class ShellSort {

    public static void main(String[] args) {
        int[] A = {32, 13, 13, 1,223,6,234,223243,12,112,1};
        shellSort(A, A.length);
        for (int i : A) {
            System.out.print(i+" ");
        }
    }

//    间隔为g
    static void insertionSort(int[] a, int n, int g){
        for(int i=g; i<n; i++){
            int temp = a[i];
            int j = i-g;
            while (j>=0 && a[j]>a[i]){
                a[j+g] = a[j];
                j-=g;
            }
            a[j+g] = temp;
        }
    }

    static void shellSort(int[] a, int n){
        int[] G = {1,2,3,4};
        for(int i=G.length-1; i>0; i--){
            insertionSort(a, n, G[i]);
        }
    }

}