排序

• 选择排序
  • 简单选择排序
  • 在未排序序列中找出最小元素与序首元素交换位置，然后再剩下的未排序序列中找出最小元素与序列第二位元素交换位置，依次类推。
  • T(n)=O(N^2)

    for(int i=0;i<N;i++){
        int min=i;
        for(int j=i+1;j<N;j++){
            if(a[j]<a[min])
                min=j;
        }
        temp=a[i];
        a[i]=a[min];
        a[min]=temp;
   }

• 堆排序

• 堆是一种特殊的二叉树，子节点的值小于父节点的值

• 利用最大堆（最小堆）输出堆顶元素，即最大值（最小值），然后再剩下的元素重新生成最大堆（最小堆），继续输出堆顶元素，直到输出所有元素。

• 插入排序

  • 简单插入排序
  • 将待排序序列分为已经排好序的和未排好序的两个部分。
  • 初始状态时，已排序序列仅包含第一个元素，将未排序序列中的元素逐一插入到已排序的序列中，经过N-1次插入则排序完成。
  • 插入排序是相对稳定的排序，数值相同的两个记录不会发生相对位置上的变化
  • T(n)=O(N^2)

    for(int i=1;i<N;i++){
       temp=a[i];
       for(int j=i;(j>0)&&(temp<a[j-1]);j--){
           A[j]=A[j-1]    //j是从i开始的,已排好序的元素右移给腾出位置
       }
       A[j]=temp;   //插入到合适的位置
    }

• 希尔排序

  • 简单插入排序效率不高的重要原因是每次只交换相邻的两个元素，这样一次只能消去一对错位的元素。希尔排序试图通过每次交换一定距离的两个元素，达到排序效率上的提升。

• 希尔排序将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序，开始时设置的间隔较大，在每轮排序中间隔逐步减小，直到间隔为1，也就是最后一轮排序。

• 交换排序

  • 冒泡排序
  • 对元素个数为N的待排序序列，共进行N-1次循环。
  • 在第K次循环中，对从第1个元素到第N-K个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素则交换位置，否则保持位置不变，这样一次循环下来就把第K大的元素放到第N-K的位置上，称为第K趟的冒泡。
  • T(n)=O(N^2)
  • 冒泡排序也是一种稳定的排序

for(int i=0;i<N;i++){
        flag=0;              //标记这次循环是否有发生交换，若无则说明整个序列有序
        for(int j=0;j<N-i-1;i++){
           if(a[j+1]<a[j]){
              temp=a[j+1];
              a[j+1]=a[j];
                a[j]=temp;
              flag=1;
           }
        }
        if(!flag)
          break;           //若没有发生交换，则跳出循环
     }

• 快速排序

• 将未排序元素根据基准分为两个子序列，然后对两个子序列用类似的方法排序。

• T(n)=O(NlogN)

• 至少需要O(logN)深度的栈空间

• 归并排序

  • 将大小为N的序列看成N个长度为1的子序列，接下来将相邻子序列进行归并操作，形成[N/2]个长度为2（或1）的有序子序列，然后再进行相邻子序列的两两归并操作，如此一直循环知道只剩下一个长度为N的序列。
  • 需要申请额外空间用于放置两个子序列归并之后的结果
  • T(n)=O(NlogN)

• 桶排序

  • 已知N个关键字的取值范围是0-M-1；而M比N小得多，则桶排序算法将为关键字的每个可能取值建立一个桶，在扫描N个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了。
  • 桶排序效率比一般排序算法高，额外条件是已知关键字的范围i，并且关键字在此范围内是可列的个数还不能超过内存空间所能承受的限度。

• 基数排序
  基数排序是对桶排序的一种推广，所考虑的待排序记录包含不止一个关键字，例如对一副牌的整理。

• 归纳
• 排序算法性能从低到高的顺序大致为：冒泡排序、插入排序、选择排序、希尔排序、快速排序。但这个优劣顺序不是绝对的，在不同的情况下，甚至可能出现完全的性能逆转。
• 对于序列初始状态基本有正序，可选择对有序性较敏感的如插入排序、冒泡排序、选择排序等方法
• 对于序列长度 比较大的随机序列，应选择平均时间复杂度较小的快速排序方法。