C语言排序

Merge_sort_animation2.gif

  1. 直接插入排序是平安的;而希尔排序是不安宁的。
  2. 直接插入排序更切合于原始记录基本平稳的成团。
  3. Hill排序的相比较次数和运动次数都要比直接插入排序少,当N越大时,效果越强烈。
  4. 在希尔排序中,增量连串gap的里丑捧心必须满意:最终一个升幅必须是 1 。
  5. 间接插入排序也适用于链式存储结构;希尔排序不适用于链式结构。

Sorting_quicksort_anim.gif

  1. 冒泡排序
  1. 插入排序

void Shellsort(ElementType A[],int N)
{
int i,j,Increment;
ElementType tmp;
for (Increment = N/2; Increment>0; Increment/=2)
for ( i = Increment; i < N; i++)
{
  tmp = A[i];
  for ( j = i; j >= Increment; j-=Increment)
       if(tmp<A[j - Increment)
      A[j] = A[j- Increment];
    else
      break;
  A[j] = tmp;
  }
}/*使用希尔增量的希尔排序例程*/
  void Quicksort(ElementType A[],int N)
{
    Qsort(A,0,N-1);
}

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]);
    Swap(&A[Center],&A[Right-1]);
    return A[Right-1];
}/*实现三数中值分割方法的程序*/


#define Cutoff(3)
void Qsort(ElementType A[],int Left,int Right)
{
    int i,j;
    ElementType Pivot;
    if(Left+Cutoff <=Right)
    {
        Pivot = Median3(A,Left,Right);
        i = Left;j = Right-1;
        for( : : )
        {
            while(A[++j]<Pivot){}
            while(A[--j]>Pivot){}
            if(i<j)
                Swap(&A[i],&A[j]);
            else
                break;
        }
        Swap(&A[i],&A[Right-1]);
        Qsort(A,Left,i-1);
        Qsort(A,i+1,Right);
    }
    else
        InsertionSort(A+Left,Right - Left + 1);
  }/*快速排序的主例程序*/
void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
int Center;
if(Left<Right)
  {
        Center = (Left + Right)/2;
        MSort(A,TmpArray,Left,Center);
        MSort(A,TmpArray,Center+1,Right);
        Merge(A,TmpArray,Left,Center+1,Right);
  }
}

void Mergesort(ElementType A[],int N)
{
      ElementType *TmpArray;
      TmpArray = malloc(N*sizeof(ElementType));
      if(TmpArray != NULL)
     {
      MSort(A,TmpArray,0,N-1);
      free(TmpArray);
     }
     else
    FatalError("No space for tmp array!");
}/*归并排序例程*/

合计:把记录按步长 gap
分组,对每组记录选择直接插入排序方法举办排序。随着步长逐步减小,所分成的组包涵的笔录更加多,当步长的值减小到
1 时,整个数据合成为一组,构成一组有序记录,则形成排序。
直接插入排序和希尔排序的可比:

  1. 堆排序

N-1趟排序组成
C语言代码完结:

归并排序以O(NlogN)最坏意况运行时刻运作,而所拔取的比较次数大致是最优的。是递归算法的一个很好的实例。分治是递归分外有力的用法。


void(InsertionSort)(ElementType A[],int N)
{
  int j,P;
  ElementType tmp;
  for(P=1;P<N;P++)
{
    tmp = A[P];/*摸下一张牌*/
    for(j = P; j>0&&A[j-1]>tmp; j--)
        A[j] = A[j-1];/*移出空位*/
    A[j] = tmp;/*新牌落位*/
 }
}/*插入排序例程*/

插入排序为O(N^2)
N个互异数的数组的平分逆序数是N(N-1)/4

希尔排序.png

参考:

1.
程序员必须理解的10大基础实用算法及其讲解

2. 排序四
希尔排序

  1. 归并排序
  1. 希尔排序-收缩增量排序

问题:因为联合多个排序的表须要线性附加内存,在全部算法中还要消费将数据拷贝到临时数组再拷贝回来这么一些增大工作,其结果严回看慢了排序的快慢。所以很难用于主存排序。


  1. 从数列中挑出一个要素,称为 “基准”(pivot)。
  2. 再也排序数列,所有因素比基准值小的摆放在基准前边,所有因素比基准值大的摆在基准的末尾(相同的数可以到任一边)。在这么些分区退出之后,该标准就处在数列的中间地点。这几个号称分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
package notes.javase.algorithm.sort;
public class ShellSort {
public void shellSort(int[] list) {
    int gap = list.length / 2;
 while (1 <= gap) {
        // 把距离为 gap 的元素编为一个组,扫描所有组
        for (int i = gap; i < list.length; i++) {
            int j = 0;
            int temp = list[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        System.out.format("gap = %d:\t", gap);
        printAll(list);
        gap = gap / 2; // 减小增量
    }
}
// 打印完整序列
public void printAll(int[] list) {
    for (int value : list) {
        System.out.print(value + "\t");
    }
    System.out.println();
}
public static void main(String[] args) {
    int[] array = {
            9, 1, 2, 5, 7, 4, 8, 6, 3, 5
    };
    // 调用希尔排序方法
    ShellSort shell = new ShellSort();
    System.out.print("排序前:\t\t");
    shell.printAll(array);
    shell.shellSort(array);
    System.out.print("排序后:\t\t");
    shell.printAll(array);
 }
}

敏捷排序是在实践中最快的已知排序算法,它的平均运行时刻为O(NlogN)。该算法非常快的原故是不行简短和中度优化的其中循环。最坏景况的品质为O(N^2),但稍加努力就可以幸免。
三数中值分割法:清除了预排序输入的坏意况,并且减弱了长足排序大约5%的运作时刻。
对此很小的数组(N<=20)不递归地利用便捷排序,而代之以诸如插入排序那种对小数组有效的排序算法。
算法步骤:

  void BubbleSort(ElementType A[],int N)
  {
      int P,flag;
      for(P = N-1;P>=0;p--)
      {
        flag = 0;/*建立一个检查标志:在某次排序提前完成后终止循环*/
        for(int i=0;i < p;i++)/*一趟冒泡*/
        {
            if(A[i]>A[i+1])
            {
                  swap(A[i],A[i+1]);
                  flag = 1;
              }
          }
          if (flag = 0) break;
      }
  }/*冒泡排序*/

Java代码贯彻:

正文主要介绍排序的三种达成,不难总计一下复杂度。

着力格局:创造N个元素的二叉堆,费用时间O(N),然后实施N次DeletedMin操作开销时间O(log⁡N),所以总的运行时刻为O(N log⁡N)
缺点:DeleteMin操作中运用了一个数组用来囤积离开堆得元素,所以存储须求增添一倍。
C语言代码达成:
#define LeftChild(i)(2*(i)+1)
void
PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType tmp;
for(tmp = A[i];LeftChild(i)<N;i = Child)
{
Child = LeftChild(i);
if(Child!=N-1&&A[Child + 1]>A[Child])
Child++;
if(tmp<A[Child])
A[i] = A[Child];
else
break;
}
A[i] = tmp;
}
void Heapsort(ElementType A[],int N)
{
int i;
for(i = N/2;i>=0;i–)
PercDown(A,i,N);
for(i = N-1;i >0;i–)
{
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}


C语言代码完成:

  1. 快快排序

Sorting_heapsort_anim.gif