[数据结构与算法]手写数组快速排序（多种写法）

1. 简介

?快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

2. 算法步骤

① 从数列中挑出一个元素，称为 “基准”（pivot）;

② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

3. 快速排序的两种写法

?第一种写法：

	public static void sort1(int a[], int low, int hight) {  
	      // 结束的条件
	      if (low >= hight) {
	          return;
	      }
	      
	      int i, j, index;
	      i = low;
	      j = hight;
	      index = a[i]; // 此处暂用第一个元素作为基准值
	      
	      while (i < j) { 	      
	          // 先从右边进行扫描，找到大于基准值的元素
	          // 注意，此处必须先从右进行扫描，否则会影响结果正确性
	          while (i < j && a[j] >= index)
	              j--;
	          //找到之后交换
	          if (i < j)
	              a[i++] = a[j];
	              
	          //然后从左边扫描，找到小于基准值的元素
	          while (i < j && a[i] < index)
	              i++;
	          //找到之后交换
	          if (i < j) 
	              a[j--] = a[i];
	      }
	      
	      a[i] = index;
	      
	      // 对基准值左边的所有元素进行递归排序
	      sort1(a, low, i - 1);		
	      // 对基准值右边的所有元素进行递归排序
	      sort1(a, i + 1, hight);	
	  }

?第二种写法：

	public static void sort2(int a[],int low,int hight){ 
	    // 结束的条件
	    if (low >= hight) {
	        return;
	    }
	    
	    int i, j, index;
        i = low;
        j = hight;
        index = a[i]; // 此处暂用第一个元素作为基准值
        
	    while(i != j) {
		    //从右向左寻找第一个小于基准元素的数
   	        while(i < j && a[j] >= index) j--;
			//从左向右寻找第一个大于基准元素的数
	        while(i < j && a[i] <= index) i++;
	        
            // 上面的循环结束表示找到了位置或者 i >= j 了，交换两个数在数组中的位置
            if(i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
	    }
	    
        //将 i 和 j 共同指向的元素与基准元素交换
        a[low] = a[i];
        a[i] = index;
        
        //对左边进行快速排序
        sort2(a, low, i - 1);
        //对右边进行快速排序
        sort2(a, i + 1, hight);
	}

4. 有关快速排序的几个小问题（可优化的点）

?① 以上两段代码中，我们均选取数组的首元素为基准值，而对于几乎有序的数组，这样做会使得对数组的切分不够平均，可能使得快速排序的时间复杂度退到 o(n^2) ；
??为了防止这种情况，可以在排序时选取数组中的一个随机位置的数作为基准数。

?② 分而治之时候，分到了最后，数组已经很小，这时候采用插入排序代替快速排序可提高算法效率。

?③ 当数组中有很多相等元素时，也会导致快排对数组的切分不平衡，此时快排的时间复杂度也可能退到 o(n^2) ；
??对于这种情况，可以使用三路快速排序，把小于基准 v 的放左边，等于 v 的放中间，大于 v 的放右边，就避免了左右不平衡的问题。

三路快速排序：

	public static void sortThreeWays(int a[], int low, int hight){
		    // 结束的条件
		    if (low >= hight) {
		        return;
		    }
		    
		    int i, j, index, current;
	        i = low;
	        j = hight;
	        index = a[i]; // 此处暂用第一个元素作为基准值
	        current = i + 1;
	        
	        while(current <= j){
	            //如果当前元素大于基准元素，将次元素放到后面去，j--
	            if(a[current] > index){
	                int temp = a[current];
	                a[current] = a[j];
	                a[j--] = temp;
	            //如果当前元素小于 index，将它放到 i 前面去
	            } else if(a[current] < index) {
	                if (current != i + 1) {
	                	int temp = a[current];
		               a[current] = a[i+1];
		               a[i] = temp;
	                }
	                i++;
	                current++;
	            //若当前元素等于 index，当前指针 current 后移即可
	            } else {
	                current++;
	              }   
	        }
	        
	        //最后交换 arr[low](基准元素)与 arr[i] 的位置
	        int temp = a[i];
	        a[i] = a[low];
	        a[low] = temp;
	        //对基准元素左边快排
	        sortThreeWays(a, low, i-1);
	        //对基准元素右边快排
	        sortThreeWays(a, j+1, hight);
	    }

以上代码均经过测试无误，读者可自行运行测试