安安的code日記

快速排序法說明：

1.設定一個指標數

2.用兩個指標，一個「左」，一個「右」，左箭頭 往右跑時如果碰到比 指標 大的數就停下來

3.換右箭頭 往左邊跑，遇到比 指標 小的數就停下

4.如果左右箭頭還沒有碰到，就交換各自停下的數

5.兩箭頭碰到後，該位置就是指標的所在位置

6.將指標與重合處的數交換後，以重合位置為分隔點，在排列左右陣列

7.直到切割出的陣列長度為1，不用再進行排列

這個演算法我花了好多時間研究，一開始一直沒有弄懂為什麼要將參數left、right另外放進start、end的新變數裡

後來才想到要用start和end來指出下一個遞迴要排列的陣列範圍，

start要指出左邊陣列的開頭

end要指出右邊陣列的結尾

原本錯誤的code一直用 0和left-1來標示要排列的左邊陣列，結果落入無限迴圈...

這是錯誤的code！！

public class MainClass {
    public static void main(String[] args) {
        int a[] = {1, 5, 3, 4, 2};
        quickSort(a, 0, a.length - 1);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void swap(int a[], int index1, int index2) {
        int tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    public static void quickSort(int a[], int left, int right) {
        if (right <= left) {
            return;
        }
        int pivot = a[left];
        int pivotIndex = left;
        while (left < right && a[right] >= pivot) {
            right--;
        }
        while (left < right && a[left] <= pivot) {
            left++;
        }
        if (left != right) {
            swap(a, left, right);
        }
        swap(a, pivotIndex, left);


        quickSort(a, 0, left - 1);   //左邊設為0的話，排好的陣列又會被算進去了
        quickSort(a, left + 1, a.length - 1);   //右邊設為陣列尾端的話，排好的陣列又會被算進去
    }
}

正確的code

public class MainClass {
    public static void main(String[] args) {
        int a[] = {1, 5, 3, 4, 2};
        quickSort(a, 0, a.length - 1);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void swap(int a[], int index1, int index2) {
        int tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    public static void quickSort(int a[], int left, int right) {
        if (right <= left) {
            return;
        }
        int start = left;
        int end = right;
        int pivot = a[left];
        int pivotIndex = left;
        while (left < right && a[right] >= pivot) {
            right--;
        }
        while (left < right && a[left] <= pivot) {
            left++;
        }
        if (left != right) {
            swap(a, left, right);
        }
        swap(a, pivotIndex, left);


        quickSort(a, start, left - 1);
        quickSort(a, left+1, end);
    }
}