【转】快速排序

Java版本 1：

    public static void QuickSort(int[] arr,int start,int end)
    {
        if(start>end)
            return;

        int index=getIndex(arr,start,end);
        QuickSort(arr, start, index- 1);
        QuickSort(arr, index + 1, end);
    }

    //划分左右区间，即找到基准数的位置
    public static int getIndex(int[] arr, int start, int end) 
    {
        int i = start, j = end;
        int key = arr[i];
        while (i < j)
        {
            while (i < j && arr[j] >= key) 
            {
                j--;
            }
            if (i < j)
            {
                /* arr[i]已经保存在key中，可将后面的数填入 */
                arr[i] = arr[j];
                i++; //下次，从i的后一个位置开始找
            }
            /* 按i++方向遍历目标数组，直到比key大的值为止 */
            while (i < j && arr[i] < key)
            {
                i++;
            }
            if (i < j) 
　　　　　　　{
                /* arr[j]已保存在arr[i]中，可将前面的值填入 */
                arr[j] = arr[i];
                j--; //下次，从j的前一个位置开始找
            }
        }
        /* 此时i==j */
        arr[i] = key;
        return i;
    }

Java版本 2（推荐版本）：其实就是版本 1的紧凑型（版本 2 QuickSort( )的末尾找到位置 i 之后直接利用了它，而版本 1 要返回之后再调用。）

public static void QuickSort(int[] arr, int low, int high)
    {
        if (low >= high) //这个判断非常重要，没有的话，将不能正常结束函数。
        {
            return;
        }
        int i = low;
        int j = high;
        int key = arr[low];

        while (i < j)
        {
            while (i < j && key <= arr[j])
            {
                j--;
            }

            arr[i] = arr[j];
            while (i < j && key >= arr[i])
            {
                i++;
            }

            arr[j] = arr[i];
        }

        arr[i] = key;
        QuickSort(arr, low, i - 1);
        QuickSort(arr, i + 1, high);
    }

实现2 参考自：快速排序--百度百科 C语言版本：

void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
     
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
         
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
         
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}