快速排序

快速排序

排序前提条件：

快速排序是一种不稳定的排序

排序的量大（大约大于100），否则效率没有简单排序高

原理：

分而治之

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

自己的一些小疑问：

为什么在主函数内递归使用排序算法，就能保证每一个出来的都是有序的。

憨憨一样，出来不是有序的是什么。

其实在我脑子里面最根本的疑问是递归的将一个一个子集使用同一个函数，会占用很大的内存。

不过这也是快速排序的缺点。

优点：

很明显，量大时快速排序是算法中比较快的

缺点：

内存使用量大，

数量少时排序效率低下

过程：

1.判断是否需要使用快速排序。

2.选出Pivot，一般采用前，中，后三个数的中位数。 并且在函数中，将前，后两个数提前排好位置，并将Pivot放在最后（坐标为Right-1）。

3.定义双指针，两个指针 i，j 分别从前后遍历（从Left-1 ~ Right-2，共n-1个数）。

4.左边的指针向右寻找比Pivot大的数，找到后，右边的指针向左寻找比Pivot小的数，找到后交换i，j两个位置元素的值（如果i>j，说明：左指针 在 右指针的右边，递归结束）

ElementType Median3( ElementType A[], int Left, int Right )
{ 
    int Center = (Left+Right) / 2;
    if ( A[Left] > A[Center] )
        Swap( &A[Left], &A[Center] );
    if ( A[Left] > A[Right] )
        Swap( &A[Left], &A[Right] );
    if ( A[Center] > A[Right] )
        Swap( &A[Center], &A[Right] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}
 
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;
       
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选基准 */ 
          Low = Left; High = Right-1;
          while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ 
}
 
void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
     Qsort( A, 0, N-1 );
}

快速排序

原文：https://www.cnblogs.com/lanyun1103/p/11892694.html