内排序与外排序

内排序：在排序的过程中，待排序的所有记录全部被放置在内存中。
外排序：由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

  • 时间性能： 内排序中，主要是两种操作：比较和移动
  • 辅助空间：是除了存放待排序所占的存储空间之外，执行算法所需要的其他存储空间
  • 算法的复杂性：指算法本身的复杂度

内排序：插入排序、交换排序、选择排序、归并排序

七种排序方法：冒泡排序、简单选择排序、直接插入排序、希尔排序、堆排序、归并排序快速排序

1. 冒泡排序

冒泡排序（Bubble Sort） 一种交换排序

基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

关键思想： “两两比较相邻记录”

双重循环，i , j

  1. void BubbleSort(SqList *L)
  2. {
  3.     int i,j ;
  4.     for (i=1 ; i<L->length;i++)
  5.     {
  6.         for(j = L->length-1;j>=i;j--)  /*注意j是从后往前循环*/
  7.         {
  8.             if (L->r[j] > L->r[j+1])  /*若前者大于后者*/
  9.             {
  10.                 swap(L,j,j+1); /*交换L->r[j] 与 L->r[j+1]的值*/
  11.             }
  12.         }
  13.     }
  14. }

优化
{2,1,3,4,5,6,7,8,9}
**
#针对部分已经排好序的，增加一个flag 来优化

  1. void BubbleSort(SqList *L)
  2. {
  3.     int i,j ;
  4.     Status flag = TRUE;
  5.     for (i=1 ; i<L->length  && flag ;i++)   /*若flag为true则说明有过数据交换*/
  6.     {
  7.         flag = FALSE;
  8.         for(j = L->length-1;j>=i;j--)  /*注意j是从后往前循环*/
  9.         {
  10.             if (L->r[j] > L->r[j+1])  /*若前者大于后者*/
  11.             {
  12.                 swap(L,j,j+1); /*交换L->r[j] 与 L->r[j+1]的值*/
  13.                 flag = True;  /*如果有数据交换，则flag为true*/
  14.             }
  15.         }
  16.     }
  17. }

2. 简单选择排序

初步思想：在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作

选择排序的基本思想：每一趟在n-i+1(i=1,2,3,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录

简单选择排序算法

通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个（1<= i <= n)个记录交换之。比较多次，交换一次。 时间复杂度依然为 O(n^2)

先定最小值，然后后面再进行比较

  1. void SelectSort(SqList *L)
  2. {
  3.     int i,j,min;
  4.     for(i=1;i<L->length;i++)
  5.     {
  6.         min = i;                /*将当前下标定义为最小下标*/
  7.         for (j = i+1;j<=L->lengtn;j++)  /*循环后面的数据*/
  8.         {
  9.             if (L->r[min] > L->r[j])         /*如果有小于当前最小值的关键字*/
  10.                 min =j;                    /*将此关键字的下标赋值给min*/
  11.         }
  12.         if (i != min )
  13.             swap(L,i,min);
  14.     }
  15. }

3. 直接插入排序

算法思想：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表

  1. void InsertSort(SqList *L)
  2. {
  3.     int i ,j;
  4.     for (i=2 ;i <L->length;i++)   /*i = 2开始，假设r[1] 已经放好位置，后面的牌其实就是插入到它的左/右
  5.     {
  6.         if (L->r[i] < L->r[i-1])   /*需将L->r[i] 插入有序表*/
  7.         {
  8.             L->r[0] = L->r[i]  /*设置哨兵*/
  9.             for (j = i-1;L->r[j] > L>r[0];j--)
  10.                 L->r[j+1] = L->r[j];  /*记录后移*/
  11.             L->r[j+1] = L->r[0]; /*插入到正确的位置*/
  12.         }
  13.     }
  14. }
  16. #{0,5,3,4,6,2}  r[0] = 0 用于哨兵作用
  17. #这里的关键 是区分 i 和 j 的作用

4. 希尔排序

思路：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序 跳跃式前移

  1. void ShellSort(SqList *L)
  2. {
  3.         int i,j;
  4.         int increment = L->length;
  5.         do
  6.         {
  7.             increment = increment / 3 +1; /*增量序列*/
  8.             for (i =increment + 1;i<= L->length；i++)
  9.             {
  10.                  if（L->r[i] < L->r[i-increment])
  11.                  {
  12.                      /* 需将L->r[i]插入有序增量子表*/
  13.                      L->r[0] = L->r[i] ; /*暂存在L->r[0]*/
  14.                      for (j = i-increment;j > 0 && L->r[0] < L->r[j]; j -= increment)
  15.                          L->r[j+increment] = L->r[j]; /*记录后移，查找插入位置*/
  16.                      L->r[j+increment] = L->r[0]; /*插入*/
  17.                  }
  18.             }
  19.             while(increment > 1);          /*增量等于1时就停止循环了*/
  21.             }

注：希尔排序不是随便分组后各自排序，而是将相隔某个‘增量’的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。

5. 堆排序

堆 是 具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

注：根节点 一定是堆中所有结点最大（小）者

Ki >= K2i
Ki >= K2i+1

Ki <= K2i
Ki <= K2i+1

1<= i <=[n/2]

思路：
堆排序 （Heap Sort） 就是利用堆进行排序的方法
将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是顶堆的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的N-1 个序列重新构造成一个堆，这样就会得到N个元素中的次大值，如此反复执行，便能得到一个个有序序列了。

两个问题：
1.如何由一个无序序列构建成一个堆？
2.如果在输出堆顶元素后，调整剩余元素成为一个新的堆?

  1. void HeapSort(SqList *L)
  2. {
  3.     int i;
  4.     for (i= L->length/2;i>0;i--)  /*把L中的r构建成一个大顶堆*/
  5.         HeapAdjust(L,i,L->length);
  7.     for (i=L->length;i>1;i--)
  8.     {
  9.         swap(L,1,i); /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
  10.         HeapAdjust(L,1,i-1); /* 将L->r[1..i-1] 重新调整为大顶堆 */
  11.     }
  12. }