排序

按照C的约定，对于所有排序，数据都将在位置0处开始。

对于数字可使用“<”和“>”；对于字符串使用strcmp和strcpy。

排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

O(n2)

稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

Shell

O(nlogn)

O(n^1.25)

O(ns) 1<s<2

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

堆

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

一、冒泡排序

作为排序的启蒙算法，回顾一下逝去的青春岁月。。。

void bubbleSort(elementType A[], int N)
{
       int i,j;
       for(i = 0; i < N; i++)    //第一趟，A[0]与其余元素比较，将最小元素交换给A[0]
       for(j = i+1; j < N; j++)
       {
           if(A[i] > A[j])
           swap(&A[i], &A[j]);
       }
}
void swap(elementType *a,elementType *b)
{
       elementType c;
        c =  *a;         //字符串，可以使用strcpy(c, *a);  
       *a =  *b;
       *b =   c;
}

二、插入排序

插入排序有N-1趟排序组成。对于P = 1趟 到P = N-1趟，插入排序保证对于每趟P，位置0到位置P上的P+1个元素已排序。

由此可知：

对于每趟P，位置P之前的元素已经为有序状态。只需要将位置P上的元素保存并依次与其前元素比较，比其大的元素依次后移，将位置P上元素插入到合适位置，保证前P+1个元素为有序状态。

void insertionSort( elementType A[] , int N)
{
       int j ,p;
       elementType tem;
       for( p = 1 ; p <= N-1; p++)
       {
            tem = A[p];      //保存位置p上的数据到tem，则位置p为空位，其前元素大于tem的，则依次后移一位。
            for(j = p; j - 1>=0 && A[j-1] > tem; j--)
                A[j] = A[j-1];
            A[j] = tem;
       }
}

三、希尔排序

插入排序是连续的子序列，而希尔排序是跳跃的子序列，跳跃的幅度取决于增量大小。

其中增量为Hibbard增量时，最坏时间复杂度为Θ（N3/2）。

Hibbard增量形如：1 , 3 , 7 , ... , 2k-1. (增量之间没有公因子)

void shellSort (elementType A[], int N)
{
        int i , j , increment;
        elementType tem;
        //prevPrime(S)表示小于S的最大素数
        for( increment = prevPrime(N/2); increment > 0; increment /=2)
              for( i = increment; i < N; i++)
              {
                   tem = A[i];
                   for(j = i; j >=increment; j -= increment)
                       if(tem < A[j - increment])
                          A[j] = A[j - increment];
                       else
                           break;
                   A[j] = tem;
              }
              
}

 四、堆排序

堆是一个完全二叉树，可以用一个数组表示；

a[0]存放一个值（最大堆时，这个值要足够大），堆中元素从下标1开始存储。

对于任一个父亲结点：i，左孩子：2*i，右孩子：2*i+1；

对于任一个孩子结点：i，其父亲结点都是i/2；

两个思路：

1、建立最大堆，每次删除堆顶元素，保存到新的数组，新的数据就是降序排列，将数组复制回原数组即可。由于建立新的数组，空间复杂度增加了。

2、在建立最大堆后，每次删除堆顶元素，保存到堆的末尾处（2-1指针和2-2数组两种方式）

2-1：指针方式

插入即之前二叉堆的上滤的过程：

for (i = ++H->size; H->elements[i/2] > X; i /= 2 )
      H->elements[i] = H->elements[i/2];
H->elements[i] = X;

这样就建立了一个最小堆。

在删除最小元素时，需要将代码稍加修改：

a. 堆的原始大小H->size保持不变，可以用一个整型替代，并以形参传递

b. 保持每次删除的最小元素

elementType deleteMin(priorityQueue *H, int& N)
{
         int i, child;
         if(isEmpty(H))
         {
               cout << "priotity queue is empty" << endl;
               return H->elements[0];
         }
         minElement = H->elements[1];
         lastElement = H->elements[ N-- ];
         for(i = 1; 2*i <= N; i = child)
         {
               child = 2*i;
               if(child != N && H->elements[child +1] < H->elements[child])
                  child ++;
               if(H->elements[child] < lastElement)
                  H->elements[i] = H->elements[child];
               else             //不写的话，在最小堆下，i的取值也不会满足循环条件
                    break;   
         }
         H->elements[i] = lastElement;
         return minElement;
}

堆排序：

priorityQueue* heapSort(priorityQueue *H)
{
           for(int N = H->size; N > 0; N--)
           {
               H->elements[++N] = deleteMin(H, N);  //N是实参，即H->size
　　　　　　 }
 　　　　　　return H; 
}

2-2数组方式

直接进行堆排序，即默认已经存在一个完全二叉树，我们需要将其排成最大堆（孩子与父亲结点的交换），

然后将最大元素放在数组末端，即交换第一个和最后一个元素，然后对前N-1个元素再一次建立最大堆；

所以，先写一个建立最大堆的公共接口。

建立最大堆的方法：即最大堆原始定义：孩子结点都小于父亲结点，否则交换两者数据；

技巧：如果存在两个孩子选出最大的出来，跟父亲结点交换。

从下标0开始存储数据，此时，对于元素i，左儿子2*i+1，右儿子2*i+2;

#define leftChild(i)  (2*(i)+1)  //i = N-1时，(i)的优势就体现出来了

void interChange(elementType A[], int i, int N)
{
        int child;
        elementType tem;
        for(tem = A[i]; leftChild(i) < N; i = child)
        {
              child = leftChild(i);
              if(child != N && A[child+1] > A[child])
              　 child++;
              if(tem < A[child])      //保证在任意数组下，建立起最大堆
              　 A[i] = A[child];
              else
                   break;
        }
         A[child] = tem;
}
void heapSort (elementType A[], int N)
{
       int i; 
       for(i = N/2; i >=0; i--)  //也可以用for(i = 0;2*i<N;i++)
            interChange(A, i, N);     //builfMaxHeap

       for(i = N-1; i > 0; i--)
       {
             swap(&A[0], &A[N-1]);  　　　　　　//deleteMax
             interChange(A, 0, i );            //在堆序性下，删除了最大元素后，只需要调整堆顶及其孩子的堆序即可
       }     
}

五、归并排序

归并排序以O(NlogN)最坏情形运行时间运行。比较次数几乎是最优的。他是分治思想的一个好例子。

若N=1，则无需排序。否则，递归地将前半部分数据 和 后半部分数据 各自归并排序，最后将这两部分合并。

合并方法：

从头依次比较 前后两半数据的数组A和B 并将较小者保存至 一个新的数组C中，下标自增；

直到A或B其中一个数组中元素全部在C中，最后将剩余有序元素依次保存在C中。

改进的方法就是将原始数组分为A和B两个数组，最后将C赋值回原数组即可。

//归并是左右开弓，无限拆分；实际排序部分由merge()完成。

void mSort(elementType A[], elementType tem[], int left, int right)
{
       int center;
       if(left < right)        //left == right,只有一个元素在A中，无需排序
       {
          center = (left + right)/2;
          mSort(A, tem, left, center);           //左部分排序  这些都是实参，即实际数值
          mSort(A, tem, center+1, right);    //右部分排序
          merge(A, tem, left, center+1, right); //left:左开，center:左结束；center+1:右开，right:右结束
       }
}

//主程序
void mergeSort(elementType A[], int N)
{
       elementType *tem;
       tem = (elementType *)new elementType[N];
       if(tem == NULL)
       {
          cout <<"out of space!" << endl;
       }    
       else
       {
           mSort(A, tem, 0, N-1);         //主程序前，先定义mSort();
           delete(tem);                   //指针回收
       }
}

//合并程序merge的实现
void merge(elementType A[], elementType tem[], int leftStart, int rightStart, int rightEnd)
{
       int i, leftEnd, totalNum,temStart;
       leftEnd = rightStart - 1;
       temStart = leftStart;           //原数组排序未必从位置0开始，tem数组的起始位置跟原始数组保持一致，方便最后回传数据
       totalNum = rightEnd - leftStart +1;
       //main loop
       while(leftStart <= leftEnd && rightStart <= rightEnd)
             if(A[leftStart] <= A[rightStart])
                tem[temStart++] = A[leftStart++];
             else  
                tem[temStart++] = A[rightStart++];
       //the rest elements
       while(leftStart <= leftEnd)
             tem[temStart++] = A[leftStart++];
       while(rightStart <= rightEnd)     
             tem[temStart++] = A[rightStart++];
        //return data back to A
        for(i = 0; i < totalNum; i++, rightEnd--)  //以上变量只有，leftEnd和rightEnd值为变，由于原始数组未必从0开始，所以不可以从0开始赋值
            A[rightEnd] = tem[rightEnd];
}

 六、快速排序

quickSort是实践中最快的已知排序算法，平均运行时间O(NlogN)。

1、如果A中元素个数为0或1，则返回。

2、在A中取一个枢纽元pivot，利用三数中值分割法，将left,center,right上的元素进行比较，A[left]最小，A[right]最大。swap(&A[center],&A[right-1])将pivot保存在A[right]中。

3、N<=3，插入排序；N>=4快排。

三数中值分割法：

elementType median3(elementType A[], int left, int right)
{
             int center;
             center = (left + right) / 2;
             if(A[left] > A[center])
                swap(&A[left], &A[center]);
             if(A[center] > A[right])
                swap(&A[center], &A[right]);
             if(A[left] > A[center])
                swap(&A[left], &A[center]);
             swap( &A[center], &A[right - 1]);  //将pivot保存在A[right-1]中
             return A[right - 1];
}

主程序：

#define offset (3)
void quickSort(elementType A[], int left, int right)
{
        int i, j;
        elementType pivot;
        if(left + offset <= right)    //right - left + 1 >= 4;
        {
           pivot = median3(A, left, right);
           i = left; 
           j = right - 1;
           while(1)
           {
                while (A[++i] < pivot){}
                while (A[--j] > pivot){}
                if(i < j)
                   swap(&A[i], &A[j]);
                else
                   break;  //最后由于 ++i 终止，则 i == j;最后由于--j 终止，则 i - 1 = j。 A[i]中保存着从左到右第一个大于pivot的数，交换A[i]和A[right - 1]值，将pivot值保存在A[i]中。
           }
           swap(&A[i]) , &A[right - 1]);  //将pivot值保存在A[i]中
           quickSort(A, left, i - 1);    
           quickSort(A, i +1, right);
         }
         else 
             insertSort(A, right - left +1);
}

快排-剑指版：

数组中随机找一个数字将数组分成两部分，使得比选择数字小的移到数组左边，比选择数字大的移到数组右边。

int index = start + rand()%(end - start + 1);  index属于[start , end]区间的一个随机数;

int Partition(int data[], int length, int start, int end)
{
     if(data == NULL || length <= 0 || start < 0 || end >= length)
         throw new std::exception("Invalid Parameters");  
     int index = RandomInRange(start , end);   //随机找一个值
     Swap(&data[index] , &data[end]);             //将随机找的元素放在最后一个

      int pivot = start - 1;     //用于保存随机元素的位置
      for(index = start; index < end; ++index)
      {
           if(data[index] < data[end])
           {
              ++pivot;                             //pivot存放最后一个比随机值小的数字
              if(pivot != index)
                 Swap(&data[index] , &data[pivot]);
           } 

      }
      ++pivot;  //pivot是第一个大于随机数的下标
      Swap(&data[pivot] , &data[end]);
      return pivot;    //随机值的下标
}
void QuickSort(int data[], int length, int left, int right)
{
        if (start == end)       //异常情况
            return;
        int index = Partition(data, length, start, end);  //返回随机值下标，并左右满足快排规则
        if(index > start)
           QuickSort(data, length, start, index - 1);  
        if(index < end)
           QuickSort(data, length, index+1, end);
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Lunais/p/5604343.html