排序算法小论

概念：

排序： 将一个数据元素的任意序列重新排列成一个按关键字有序的序列；

内部排序： 待排序的记录存放在计算机的内存中所进行的排序操作称为内部排序；

外部排序： 待排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中需要访问外存的排序过程称为外部排序；

稳定的排序： 比如一个序列是“1,4,3,3,2”，按从小到大排序后变成“1,2,3,3 ,4”，就叫做稳定排序，即3和3*相对顺序不变。

时间复杂度一般由比较和移动次数决定

一、插入排序

1、直接插入

基本思想： n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。

2、二分插入

折半插入排序仅减少了比较元素的次数，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n，而元素的移动次数并未改变，它依赖于待排序表的初始状态；
时间复杂度仍为O(n²)；

void   InsertSort(SqList &L)   /* 对顺序表L作折半插入排序 */
{	
        for(i=2；i <= L.length; i++) 
        {   L.r[0] = L.r[i];                /* 保存待插入元素 */
             low = 1；high = i-1；    /* 设置初始区间 */
             while(low <= high)       /* 确定插入位置 */
             {   mid = (low+high)/2；
                  if (L.r[0].key > L.r[mid].key)
                       low = mid+1；      /* 插入位置在高半区中 */
                  else  high = mid-1；   /* 插入位置在低半区中 */
             }/* while */
             for(j = i - 1; j >= high +1;  j--) /* high+1为插入位置 */
                 L.r[j+1] = L.r[j];          /* 后移元素，留出插入空位 */
             L.r[high+1] = L.r[0];      /* 将元素插入 */
         }/* for */
}/* InsertSort */

3、希尔排序

算法思想： 先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

void ShellInsert(SqlList &L, int dk){
	for(int i=dk+1; i<=L.length;i++){//把所有组都遍历一遍
		if(L.r[i].key<L.r[i-dk].key){
			L.r[0]=L.r[i];
			for(int j = i-dk; j>0&&L.r[0].key<L.r[j].key; j-=dk){
				L.r[j+dk]=L.r[j];//后挪
			}
			L.r[j+dk]=L.r[0];//插入
		}
	
	}
}

最终增量dk的值一定是1，不然没办法把整个序列都排序

二、交换排序

1、冒泡排序

2、快速排序

快排是目前所有内排序算法中速度最快的一种