快排是比较经常用到的排序方法,注意其的实现方式

  1. 基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。(递归思想)

  2. 为什么比较优秀?:每一趟循环,确定了一个关键字的位置(和冒泡排序相同)并且充分利用了比较的过程使得关键字前后两部分相对有序(一部分比另一部分大)减少了比较次数和移动次数

  3. 代码实现

    1. QuickSort(List *L)包括两个函数:1,用于递归调用的Qsort(List *L,jint low ,int high),以及使关键字到位从而分割序列的Partition(L,low,high)

       void Qsort(List *L,int low,int high)//对从low到high的序列进行排序//
       {
           if(low<high)
           {
           	int pivot;//枢纽值,在这里只是一个临时变量//
           	pivot=Partition(L,low,high);//算出枢纽值,能够将序列分割//
           	Qsort(L,low,pivot-1);//对低子表递归排序//
               Qsort(L,pivot+1,high);//对高子表递归排序//
           }//递归的过程//
    
       int Partition(List *L,int low,int high)
       {
           int pivotkey//储存枢纽记录,为了方便这里取序列的第一个//
               privotkey=L->r[low]//注意:接下来的枢纽的位置可能改变为high或者low的位置,但是枢纽的值一直都不变//
               while(low<high)
               {
                   while(low<high&&L->r[high]>=pivotkey)high--;//high哨兵从后往前扫//
                   swap(L,low,high)//找到比枢纽记录小的,前后对调,注意:对调之后枢纽记录在high所在的位置了//
                     while(low<high&&L->r[low]<=pivotkey)low++;//low哨兵从后往前扫//
                   swap(L,low,high)//找到比枢纽记录小的,前后对调,最后一次的话,low扫到和high相同的位置,进行调换后位置不变,所以下面是return low//
               }//不断循环,注意:枢纽位置从low开始取,所以应该先动high哨兵//
           return low;//返回枢纽所在的位置//
       }
    
  4. 快速排序在最优的情况下,时间复杂度为O(nlogn),最坏的情况O(n²),空间复杂度:递归造成的栈空间的使用,最好情况O(logn),最坏情况O(n)

  5. 注意:在小数组排序的时候,不如直接插入排序更好(直接插入排序是简单排序中性能最好的)。其原因是快速排序用到了递归操作。