排序

桶排序

定义n个桶，桶中有多少个数来判断这个数在数组中出现过几次，从第一个桶开始遍历可以进行排序。

#include <stdio.h>

int main(){
  int book[1001],i,j,t,n;
  for(i = 0; i<=1000;i++){
    book[i]=0;
    scanf("%d",&n);//输入一个数n，表示接下来有n个数
    for(i=1;i<=n;i++){ //循环输入n个数，并进行桶排序
      scanf("%d ",&t);//把每个数写进变量t中
      boot[t]++;//进行计数，对编号为t的桶放一个数
    }
    for(i=1000;i>=0;i--){ //依次判断编号1000-0的桶
      for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次
        printf("%d",i);

    getchar();getchar();
    return 0;
    }
  }
}

时间复杂度：O(M+N)
这个是简化版的桶排序，真正意义上算不上排序算法，如果遇到按照分数排序打印姓名就不行了。

冒泡排序

每次比较两个相邻的元素，如果它们的顺序错误就把它们交换。

#include <stdio.h>

int main(){
  int a[100],i,j,t,n;
  scanf("%d",&n);//输入一个数n，表示接下来有n个数
  for(i=1;i<=n;i++){ //循环输入n个数到数组a中
      scanf("%d",&a[i]);
  }
  //核心部分
  for(i = 1;i<=n-1;i++){ //n个数排序，只用n-1趟
    for(j=1;j<=n;j++){//从第一位开始比较直到最后一个尚未归位的数
      if(a[j]<a[j+1]){//比较大小并交换
        t=a[j];  a[j]=a[j+1]; a[j+1]=t;
      }
    }
  }
  for(i=1;i<=n;i++){
    printf("%d",&a[i]);  
  }
getchar();getchar();
return 0;
}

冒泡排序的核心思想是双重嵌套循环。时间复杂度为O(N²)。

快速排序

选择一个基准数，先从右往左找小于基准数的数，再从左往右找大于基准数的数，然后交换它们。当他们探测到同一个数时，将基准数和它进行交换。第一趟下来会分成左右两个序列，左边都是小于基准数，右边都是大于基准数，然后分别进行上一次的操作。

#include <stdio.h>
int a[101],n;

void quicksort(int left,int right){
  int i,j,t,temp;
  if(left>right)
    return;
  temp=a[left]; //temp存基准数
  i=left;
  j=right;
  while(i!=j)
  {
    while(a[j]>=temp && i<j) //从右往左
        j--;
    while(a[j]<=temp && i<j) //从左往右
        i++;
//交换两个数在数组中的位置
    if(i<j)
    {
      t=a[i];
      a[i]=a[j];
      a[j]=t;
    }
  }
//将基准数归位
  a[left]=a[i];
  a[i]=temp;

  quicksort(left,i-1);//继续处理左边的,递归
  quicksort(i+1,right);//继续处理右边的,递归
  return;
}

int main(){
  int i,j;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }
  quicksort(1,n);

  for(i=1;i<=n;i++){
    printf("%d",a[i]);
  }
  getchar();getchar();
  return 0;
}

一种错误的方法

通常的、没有经过充分考虑的选择是将第一个元素做为"基准“。如果输入书随机的，那么这是可以接受的，但是如果输入是预排序的或是反序的，那么这样的”基准“就是一个劣质的分割，因为所以的元素不是被划入S1就是被划入S2。实际上，如果第一个元素用作”基准“而且输入是预先排序的，那么快速排序花费的时间将是二次的，可是实际上却没干什么事，因此，使用第一个元素作为”基准“是绝对糟糕的。

一种安全的方法

一种安全的方法是随机选取”基准“。这种策略是非常安全的，除非随机生成器有问题，但是随机数的生成一般是昂贵的，减少不了算法其余部分的平均运行时间。

三数中值分割法

一组N个数的中值是第[N/2]个最大的数。”基准“的最好选择是数组的中值。但是这很难算出，且减慢快速排序的速度。这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为”基准”而得到。实际上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为“基准”。
实现三数中值分割方法

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];
}