目录

1.冒泡排序：

冒泡排序简单优化：

2.简单选择排序：

3.直接插入排序：

插入排序优化：二分插入排序

4.希尔排序（直接插入排序的一种优化）：

5.快速排序：

swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

                    （为方便阅读代码，每段代码前定义这个函数用来交换两个数。）

1.冒泡排序：

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

                                                              ↓基本代码↓

int main(){
	int num=10,i,j;
	int a[num]={2,9,8,3,4,8,1,7,5,6};
	for(i=0;ia[j+1])swap(&a[j],&a[j+1]);
		}
	}
	for(i=0;i 
 
      （这样的冒泡程序存在一个缺点，即序列在循环过程中有序后程序仍会继续进行。）
 
 
冒泡排序简单优化： 
 
        增加一个标记变量flag，让序列有序后自动停止。
 
 
                                                             ↓优化后的代码↓
 
 
int main(){
	int num=10,i,j,flag=1;
	int a[num]={2,9,8,3,4,8,1,7,5,6};
	for(i=0;ia[j+1]){swap(&a[j],&a[j+1]);flag = 1;}
		}
	}
	for(i=0;i 
 
 

2.简单选择排序：

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

                                                             ↓基本代码↓

int main(){
	int num=10,i,j,min;
	int a[num]={2,9,8,3,4,8,1,7,5,6};
	for(i=0;ia[j])min=j;
		}
		if(i!=min)swap(&a[i],&a[min]);
	}
	for(i=0;i 
 
分析：从过程来看，简单选择排序的最大特点是交换移动数据的次数很少。
 

3.直接插入排序：

-直接插入排序的基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

形象的描述如图：设初始数列为5 3 4 6 2 设s[6]={0,5,3,4,6,2}

数列下标     s[0] s[1] s[2] s[3] s[4] s[5](设置s[0]作为跳板，默认s[1]已经放好位置) 
初始数列      X    5    3    4    6    2  
                    
第一次排序    3    5    X    4    6    2  (比较a[2]与a[1]→3比5小故将3放在a[0] )
                                          
              X    3    5    4    6    2  (通过for循环将数列调整并复原)

第二次排序    4    3    5    X    6    2  (比较a[3]与a[2]→4比5小故放在a[0] )
                                  
              X    3    4    5    6    2  (通过for循环将数列调整并复原)

第三次排序    X    3    4    5    6    2  (比较a[4]与a[3]→6比5大故不进行操作) 

第四次排序    2    3    4    5    6    X  (比较a[5]与a[3]→2比6小故放在a[0] )

              X    2    3    4    5    6  (通过for循环将数列调整并复原，数列有序)

                                                             ↓基本代码↓

#include 
int main(){
	int s[6]={0,5,3,4,6,2};    //建立数组，注意设置跳板s[0]。 
	int i,j;
	for(i=2;i<6;i++){
		if(s[i]s[i-1]才进行操作。 
			s[0]=s[i];         //s[0]赋值。 
			for(j=i-1;s[j]>s[0];j--)s[j+1]=s[j];   
			s[j+1]=s[0];       //这两行目的是调整并后移记录。 
		}
	}
}

分析：与上述两个排序方法相比，相同的时间复杂度，直接插入排序的性能更好。

插入排序优化：二分插入排序

        由于在直接插入排序过程中，待插入数据左边的序列总是有序的，针对有序序列，就可以用二分法去插入数据了，也就是二分插入排序法。适用于数据量比较大的情况。

-二分插入排序法基本思想：（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

4.希尔排序（直接插入排序的一种优化）：

前言：

        直接插入排序在记录少或序列内基本有序时效率高，但当序列数目大，序列非常无序时效率一般。

           这时可以考虑将整个序列分割成多个子序列，在这些子序列内分别进行插入排序。但例如数列{ 9，1，5，8，3，7，4，6，2 }，分成三组{ 9，1，5 }，{ 8，3，7 }，{ 4，6，2}排序再组合之后的{ 1，5，9，3，7，8，2，4，6 }仍然杂乱无章。此时就可以考虑跳跃分割的思想，就有了希尔排序。

-希尔排序基本思想：跳跃分割，即将相距某个“增量”的记录组成一个子序列后再排序，这样就保证了在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。（如图所示）  

   

                                                              ↓基本代码↓

void Shellsort(arry[],int length)
{
	int i,j,k=0;
	int increment=length;          //设置增量increment 
	do
	{
		increment=increment/3+1;   //增量每次取之前的三分之一 
		for(i=increment;i<=length;i++)    //分组进行插入排序 
		{
			if(arry[i]0 && arry[0]

5.快速排序：

-快速排序基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，最终使整个序列有序。

（简单来说，就是先任选一个数作为支点pivot，将剩下的数分成比pivot大和比pivot小的两部分，小的部分放左边，大的部分放右边。若有一个部分只剩一个数，则这部分排序结束。否则继续对两部分分别重复上述操作指导整个序列有序。）

-代码实现：（以数组arry[6]=19,97,9,17,1,8为例）

        1.选取两个下标L（left）和R（right），分别对应数组第一个数和最后一个数。

        2.方便起见，将第一个数也就是arry[0]作为pivot。此时可以认为arry[0]是空的（如图所示）。

                           

         3.判断R指向的数：若小于pivot则将R指向的数放在L，然后进行第4步；若大于pivot则数不动，R向左退一位，重新进行第3步。直到L与R重合，将pivot放在重合的位置。

        4.判断L指向的数：若大于pivot则将L指向的数放在R，然后进行第3步；若小于pivot则数不动，R向右进一位，重新进行第4步。直到L与R重合，将pivot放在重合的位置。

                                                              （如图所示）

                           

        5.重复上述操作直到数列有序。

                                                             ↓基本代码↓

void Quicksort(int arry[],int L,int R){     //输入数组，最前下标，最后下标 
	if(L>=R) 
		return;
	int left=L,right=R;
	int pivot = arry[left];      //将arry[0]作为第一轮比较的关键数
	while(left=pivot) //部分 ① 大于pivot则数不动，R向左退一位
		{
			right--;
		}
		if(left=right)
		{
			arry[left]=pivot;
		}
	}
	Quicksort(arry,L,right-1);
	Quicksort(arry,right+1,R);//对两个部分重新进行排序 
} 

分析：快速排序的优点是排序速度快。但这个操作有个缺点，即若取得的pivot是数组中较小或较大的数，会增加很多计算量。

简单优化：三数取中，即取序列左端，中间，右端三个数进行排序，将中间值作为pivot，与数组最左端值交换，其他步骤相同。这个操作大概率减少了不必要的交换。