1.基本思想
快速排序每趟排序确定一个元素x的位置，使用的方式是 将大于元素x的值放大x的右边，小于元素x的值放大x的左边。当确定x的位置之后，再分别对x左边的数组和右边的数组进行快速排序即可。
2.算法实现
这里我使用的是递归的方法。
假设先取数组第一个元素为x，同时设i，j分别指向数组头部和数组尾部，即i=0，j=length(arr)-1;因为x取得第一个元素，所以最开始i所指向的位置即x的位置。
先从尾部j指向的元素开始比较，只要j指向的元素大于x，j便向前移一位；一旦j指向的元素小于x，就将j指向的元素放在当前x所在的位置(即当前i指向的位置)，此时可以当做x目前处于j所指向的位置。然后将x与i所指向的元素进行比较，只要i指向的元素小于x，i便向后移动一位；一旦i指向的元素大于x，就将i指向的元素放在当前x所在的位置(即当前j所指向的位置)，此时可以将x的位置认为是i指向的位置。不断循环，直到 i>=j。此时便找到了x最终的位置，即此时i，j所共同指向的位置。再将x的值填到这个位置当中，便完成了一趟快速排序。
java的代码实现如下：因为初学java，这里使用方法的时候踩了几个坑，发现静态方法中不能调用非静态成员，后来把sort改为非静态方法
public class QuickSort {
public static void main(String args[]) {
int arr[] = {6,2,10,3,8,9};
QuickSort sorter = new QuickSort();
int m = 0, n = arr.length - 1;
sorter.sort(arr, m, n);
}
public void sort(int arr[], int m, int n) {
if(m < n) {
int x = arr[m];//每次确定位置的数组元素
int i = m, j = n;
while(i < j) {//快速排序的核心,将大于x的值全放大x的右边,小于的全放在左边
while(i < j && x < arr[j]) {
j--;
}
if(x > arr[j]) {//如果j指向的数小于x，则放到x左边；if条件以防止循环因i>=j终止
arr[i] = arr[j];
}
while(i < j && x > arr[i]) {
i++;
}
if(x < arr[i]) {//如果i指向的数大于x，则放大x右边
arr[j] = arr[i];
}
}
arr[i] = x;
showArray(arr);
sort(arr, m, i-1);//对左边的部分进行快速排序
sort(arr, i+1, n);//对右边的部分进行快速排序
}
}
public void showArray(int arr[]) {
for(int x:arr){
System.out.print(x+"、");
}
System.out.println("");
}
}
python 的代码实现如下
# -*- coding: utf-8 -*- def QuickSort(lista, m, n):
if m < n:
i = m
j = n
x = lista[i]
while i < j:#第一趟排序
while i < j and x < lista[j]:
j = j - 1
if x > lista[j]:
lista[i] = lista[j]
while i < j and x > lista[i]:
i = i + 1
if x < lista[i]:
lista[j] = lista[i]
lista[i] = x#确定x位置后，将x放入该位置
print(lista)
QuickSort(lista, m, i - 1)#递归处理左边部分
QuickSort(lista, i + 1, n)#递归处理右边部分
return lista if __name__ == '__main__':
listx = [6,2,10,3,8,9]
a = 0
b = len(listx) - 1
listb = QuickSort(listx, a, b)
print(listb)
最后其实发现，每趟排序中的j--，i++部分的循环体均可以使用if语句来达到目的，但是在网上看到的博客大家都是使用循环，如果有知道的朋友欢迎给我解答