[算法]快排

原理

中心思想是用了二分法，首先取一个标致值，用这个标致值来分割两部分，一部分比它大，一部分比它小，然后就这样递归下去，直到全部的值都已经变成有序的。

上图

用图的方式更方便理解这个概念。

代码详情

第一种

 void Quicksort(int[]numbers,int left,int right)
            {
                if (left < right)
                {
                    int middle = numbers[(left + right) / 2];
                    int i = left -1 ;
                    int j = right + 1;
                    while (true)
                    {
                        while (numbers[++i] < middle) ;
                        while (numbers[--j] > middle) ;
                        if (i >= j)
                            break;
                        swap(numbers, i, j);
                    }
                    Quicksort(numbers, left, i - 1);
                    Quicksort(numbers, j+1, right);
                }
            }
void swap (int[]numbers,int i,int j)
            {
                int number = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = number;
            }

代码解释

首先我们找到一个标识值middle这个值是我们要分隔数组的中间值，然后我们定义两个下标，分别代表，比middle大的值，和比middle小的值，分别用i，j来表示，然后我们在while循环中，首先找到比middlle大的i下标的值，和比middle小的j下标的值，来调换位置，当找到i已经比j大等的时候，说明我们这次已经找完了，已经查到了middle这个值的下标，然后我们就开始分左右两个部分继续来大小划分。这时候的开始左边的区间就左边是这次的左区间加上这次找到的标识左边下标，右边区间就是标识右边的值加上当前区间的右边下标。

第二种

void Quicksort1(int [] numbers,int left,int right)
            {
                int i, last;
                if (left >= right)
                    return;
                swap(numbers, left, (left + right) / 2);
                last = left;
                for(i = left + 1; i < right; i++)
                {
                    if (numbers[i] < numbers[left])
                    {
                        swap(numbers, ++last, i);
                    }
                }
                swap(numbers, left, last);
                Quicksort1(numbers, left, last);
                Quicksort1(numbers, last+1, right);
            }
 void swap (int[]numbers,int i,int j)
            {
                int number = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = number;
            }

代码解释

首先我们把最左边的值和中间的值交换，然后我们记录下来交换的值的位置设置为last，因为我们已经把中间值和最左边的值交换了，所以我们标志值在最左边，我们就用这个值来和当前数组中的所有值来进行比较，如果比较的值比标识值小的话，就累加last然后交换，就把这个值换到了左边去了，如果大的话就不动，所以换过的左边都是比标识小的，最后当前的标识符换到最后一个最小的值的位置，那个位置之后就没有比标识值更小的了。然后再递归分割。