快排

public static void quickSort(int arr[],int start,int end) {
    int i = start, j = end;
    int temp;
    if (start < end) {
        temp = arr[start];
        while (i!=j) {
            while (i < j && temp < arr[j])
                j--;
            if (i != j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && temp > arr[i])
                i++;
            if (i != j) {
                arr[j] = arr[i];
                j--;
            }
        }
           arr[i] = temp;
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }

}

快排 quickSort
其原理就是将大于temp的数放在数组右边,小于temp的数放在左边
总体判断条件是start < end
if (start < end) 所有的操作都在其里面操作
先选择temp
temp = arr[start];
这里选择的第一个数arr[start]
如何从最后开始找到第一个比temp小的数
while (i < j && temp < arr[j])
j–;
如果找到或者直到i<j也就是i=j的情况下遍历完整个数组之后还是找到比temp小的结束循环
if (i != j) {
arr[i] = arr[j];
i++;
}

        如果i!=j也就是找到了比temp小的数则将该值存到  i 的位置,然后i++;
        然后开始进行查找比temp大的数从刚刚替换的位置后一位数开始到之前查到的那个比temp小的数中止,
        也 还是  i 至 j  因为其两侧均一定有序。
        while (i < j && temp > arr[i])
            i++;
        if (i != j) {
            arr[j] = arr[i];
            j--;
        }
        类似
        直到i==j 结束,这是将temp 放到arr[i]
          arr[i] = temp;
    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);  //递归
上一篇:常用的排序方法


下一篇:我KAO!