快速排序(Quick sort)

10大排序算法.png

快速排序在1960年由查尔斯-安东尼-理查德-霍尔(东尼-霍尔)提出,属于不稳定排序

快速排序的本质：逐渐将每一个元素都转换成轴点元素, 当轴点元素左右元素数量比较均匀的情况下复杂度是最好的，相反就是最坏情况；那为了降低最坏情况的出现概率，一般采取的做法是随机选择轴点元素

• 最好、平均时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n^2)
• 由于递归的缘故空间复杂度：O(logn)

执行流程：
1.从序列中选择一个轴点元素(pivot)
2.利用pivot将序列分隔成2个子序列

• 将小于pivot的元素放在pivot前面（左侧）
• 将大于pivot的元素放在pivot后面（右侧）
• 等于pivot的元素放哪边都可以
  3.对序列进行1、2操作，直到不能再分割(子序列中只剩下1个元素)

/**
 对[begin,end) 范围的元素进行快速排序
 */

private void sort(int begin, int end) {
       
     //0.边界条件 至少要两个元素才进行快速排序
     if(end - begin < 2) return ;

     //1.确定轴点位置
    int mid = pivotIndex(0,list.length);

    //2.对左右子序列的进行快速排序
    sort(begin,mid);//[begin,mid)
    sort(mid+1,end);//[mid,end)

}

/**
构造出[begin,end)范围的轴点元素 时间复杂度：O(n)
基本节奏
从最后一个元素开始扫描：
扫描结果如果是放在轴点左边，下一步就从左往右扫描
扫描结果如果是放在轴点右边，下一步就从右往左扫描
return: 轴点元素的最终位置
 */
private int pivotIndex(int begin, int end) {
    
   //0.随机选择一个元素跟begin位置进行交换，为了降低轴点左右不均衡的情况 
 int random = begin + (int)(Math.random()*(end-begin));//Math.random()会随机生成[0,1]的小数
 swap(begin, random);//随机交换begin位置的元素
   //1.备份begin位置的元素
   int pivot = list[begin];

   //2.end指向最后一个元素，由于是左闭右开，所以需要先--
  end--;
   
  //3.扫描
  while(begin < end) {
     
     while(begin < end) {
          //从右往左扫描，右边元素比较大 end--
         if(cmp(pivot,list[end]) < 0) {
          //这里不用<=的原因是：这样分隔出来的子序列极度不均匀，会导致出现最坏时间复杂度O(n^2)
             end--;
         }else {//右边元素 <= 轴点元素，需要放在轴点左边 然后从左往右扫描
             list[begin] = list[end];
             begin++;
             break;//跳出循环
         }
      }
      
    while(begin < end) {
          //从左往右扫描, 左边元素 < 轴点元素 这是我们想要的 begin++ 
         if(cmp(pivot, list[begin]) > 0) {
         //这里不用 >= 的原因是：这样分隔出来的子序列极度不均匀，会导致出现最坏时间复杂度O(n^2)
               begin++;
         }else {//左边元素 >=轴点元素，把元素放到右边，然后从右向左扫描
            list[end] = list[begin];
            end--;
            break;//跳出循环
         }
    }
     
  }
  
  //4.能来到这里begin==end, 将轴点元素放到最终的位置
  list[begin] = pivot;
 
 //5.返回轴点索引
 return begin;

}