快速排序的两种写法（升序和降序）

快速排序的时间复杂度为O(NlogN)，是一种不稳定的算法。

// 测试
public static void main(String[] args) {
    int[] arr = new int[]{100, 45, 99, 1, 5, 3, 88, 60, 100, 1};
    quick_sort(arr, 0, arr.length - 1);
    for(int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

//升序1
private static void quick_sort(int s[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) {// 从右向左找第一个小于x的数
                j--;
            }
            if(i < j) {
                s[i++] = s[j];
            }

            while(i < j && s[i] < x) { // 从左向右找第一个大于等于x的数
                i++;
            }

            if(i < j) {
                s[j--] = s[i];
            }
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

// 升序2
private static void quick_sort(int strs[], int l, int r) {
    if(l >= r) {
        return;
    }
    int i = l, j = r;
    int x = strs[l];
    int tmp = 0;
    while(i < j) {
        while(i < j && strs[j] >= x) { 
            j--;
        }
        while(i < j && strs[i] <= x) {
            i++;
        }
        tmp = strs[i];
        strs[i] = strs[j];
        strs[j] = tmp;
    }
    strs[i] = strs[l];
    strs[l] = tmp;
    quick_sort(strs, l, i - 1);
    quick_sort(strs, i + 1, r);
}

// 降序1
private static void quick_sort(int s[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] <= x) {// 从右向左找第一个大于x的数
                j--;
            }
            if(i < j) {
                s[i++] = s[j];
            }

            while(i < j && s[i] > x) { // 从左向右找第一个小于等于x的数
                i++;
            }

            if(i < j) {
                s[j--] = s[i];
            }
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

// 降序2
private static void quick_sort(int strs[], int l, int r) {
    if(l >= r) {
        return;
    }
    int i = l, j = r;
    int x = strs[l];
    int tmp = 0;
    while(i < j) {
        while(i < j && strs[j] <= x) {
            j--;
        }
        while(i < j && strs[i] >= x) {
            i++;
        }
        tmp = strs[i];
        strs[i] = strs[j];
        strs[j] = tmp;
    }
    strs[i] = strs[l];
    strs[l] = tmp;
    quick_sort(strs, l, i - 1);
    quick_sort(strs, i + 1, r);
}

参考资料：https://blog.csdn.net/morewindows/article/details/6684558