快速排序算法

                                                                                    快速排序算法

      本文参考清华大学出版社《数据结构与算法(C语言版)(第三版)》，详情请见书本。

        快速排序是已知排序算法中速度最快的。
        快速排序对序列S进行排序分成以下4步：
           (1)如果S中只有1或者0个元素，则返回。
           (2)在S中任意取一个元素v，称为枢纽元(pivot)。
           (3)将S-{v}分成两个不相交的集合：S1={χ∈S-{v}|χ≤v}和S2={χ∈S-{v}|χ>v}。
           (4)返回排序结果：{quicksort(S1),v,quicksort(S2)}。
        下图以例子：{5,6,2,20,8,12,16,18,1}为例，讲解算法过程：

        选取枢纽元的好坏，关系到算法性能的好坏。
        常见的选取枢纽元的方法：
            ①选择待排序序列的第一个或最后一个记录。弊端：大段序列已经预排序，使得划分的子集严重失衡。
            ②使用随机数发生器来随机选取枢纽元。弊端：产生随机数本身要花费时间。
            ③实际中常见的三数中值分割法。用任意3个数值的中值作为整个序列中值的估量值。取待排序序列的第一个记录，位置位于中间的记录和最后一个记录的中值作为枢纽元。
         待排序序列为{5,6,2,20,8,12,16,18,1}，取record[0]=5, record[4]=8, record[8]=1的中值8为枢纽元。
         三数中值分割法获取枢纽元的算法：获取枢纽元，并将其放在待排序记录的最后。

   int getPivot(int *SList, int left, int right)
   {
     int center=(left+right)/2;
     if(SList[left]>SList[center])
         swap(&SList[left], &SList[center]);
     if(SList[left]>SList[right])
         swap(&SList[left], &SList[right]);
     if(SList[center]>SList[right])
         swap(&SList[center], &SList[right]);
     swap(&SList[center], &SList[right]);
     //将pivot放在倒数第一的位置，除了可以得到pivot的右值，还能得到其左值
     return SList[right-1];
   }

       集合分割策略演示：

                                             
      快速排序算法：

   int quicksort(int *SList, int left, int right)
   {
     if(right-left>=3)
     {
       int pivot,i,j;
       pivot = getPivot(SList,left,right);
       i=left;
       j=right;
       while(true)
       {
         while(SList[i]<pivot)
           i++;
         while(Slist[j]>pivot)
           j--;
         if(i<j)
           swap(&SList[i],&SList[j]);
         else
           break;
       }
       swap(&SList[i],&SList[right]);
       quicksort(SList, left, i-1);
       quicksort(SList, i+1, right);
     }
     else     //当待排序序列长度小于3时使用直接插入排序
       straightsort(SList, right-left);
   }

       在VS2010下新建Win32 控制台应用程序的项目：QuickSort

       见下图：

       源代码：QuickSort.cpp 

// QuickSort.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"

#include<stdio.h>
#define MAXSIZE 20

  int Partition(int *SList, int low, int high)
  {
    int pivotkey=SList[low];
    while(low<high)
    {
      while(low<high && SList[high]>=pivotkey)
        high--;
      SList[low]=SList[high];
      while(low<high && SList[low]<=pivotkey)
        high++;
      SList[high]=SList[low];
    }
    SList[low]=pivotkey;
    return low;
  }

  void QSort(int *SList, int low, int high, int len)
  {
     int pivotloc;
     if(low<high)
     {
        int i;
        for(i=0; i<len; i++)
        {
          printf("%d ", SList[i]);
        }
        pivotloc=Partition(SList, low, high);
        printf("(Current pivotkey is %d) ", SList[pivotloc]);
        for(i=0; i<len; i++)
        {
          printf("%d ", SList[i]);
        }
        printf("\n ");
        QSort(SList, low, pivotloc-1, len);
        QSort(SList, pivotloc+1, high, len);
     }
  }

  void QuickSort(int *SList, int len)
  {
     QSort(SList, 0, len-1, len);
  }

  int main()
  {
    int length;
    //int pos;
    int test[MAXSIZE];
    int i;
    printf("Please input the number of record:\n");
    if(scanf("%d",&length)!=1)
      return -1;
    printf("Please input the record:\n");
    for(i=0; i<length; i++)
    {
       scanf("%d",&(test[i]));
    }
    QuickSort(test,length);
    for(i=0; i<length; i++)
    {
       printf("%d ", test[i]);
    }
    printf("\n ");

    return 0;
  }

快速排序算法

原文：http://blog.csdn.net/wp1603710463/article/details/51002267