本文发布在： ** 曲色人生，青春年华 **
一般而言，排序算法分为以下几种：
- 插入排序
- 选择排序
- 交换排序
当然还有归并等其他排序算法，这里我们主要介绍这三种。
基本概念
时间复杂度是指执行算法所需要的计算工作量，它的本质是一个函数，它定量的描述算法运行时间。算法的时间复杂度与重复操作的次数成正比，与算法语句执行的次数成正比。我们把算法中语句执行的次数称为时间频度，用T(n)来表示。
1.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
2.在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))
//1
int k = 0;
for(int i = 1;i<n; i++){
k++;
}
//这里k++ 执行了 n次；T(n)/f(n)=n/n=1;时间复杂度为:O(n);
//2.
int k = 0;
for(int i = 1;i<n; i++){
for(int j = i;j>=0;j--){
k++
}
}
//这里k++执行了 1+2+3+...n = n(n-1)/2;T(n)/f(n) = n(n-1)/2 / (n*n)≈ 0.5；因此O(n)= n^2
空间复杂度指算法占用存储空间的多少，这里不作讨论。
插入排序
插入排序从思想上来说是:把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
直接插入排序
插入排序本质上是构建有序序列，把无序序列按照顺序插入到有序序列中，首次插入默认第一个记录为有序的，即a[0]为一个只有一个记录有序序列。
算法描述：
1.默认a[0]为一个有序序列,i=0。
2.取出下一个元素(i=i+1)从后向前扫描插入到已序序列中（a[0->i-1]);
3.重复步骤2，直至i=j-1；排序完成。
| 序列 | 3 | 1 | 2 | 9 | 7 | 0 | 6 | 5 | 关键 |
|---|---|---|---|---|---|---|---|---|---|
| 第一次 | 1 | 3 | 2 | 9 | 7 | 0 | 6 | 5 | 1 |
| 第二次 | 1 | 2 | 3 | 9 | 7 | 0 | 6 | 5 | 2 |
| 第三次 | 1 | 2 | 3 | 9 | 7 | 0 | 6 | 5 | 9 |
| 第i次 | -- | -- | -- | -- | -- | -- | -- | -- | -- |
| 排序后 | 0 | 1 | 2 | 3 | 5 | 6 | 7 | 9 | -- |
算法演示：
//直接插入排序算法
void InsertSort1(int a[],int n){
int i,j,temp;
for(i=1;i<n;i++){
temp = a[i];
for(j=i-1;j>=0;j--){
if(a[j]>temp)
a[j+1] = a[j];
else
break;
}
a[j+1]= temp;
}
}
时间复杂度：O(n^2）。
备注:1+2+3+4+...n = (n-1)*n/2,去除系数时间复杂度为O(n^2);
二分插入排序
在介绍二分插入排序前先思考一个问题：对于一个有序的包含n个元素数组a[],如何寻找其中的元素k。
//直接查找
for(int i=0;i<n;i++){
if(a[i]==k)
break
}
以上方法依次把a[0],a[1],a[2],...a[n-1]和k相比较来查找k元素的，那么有没有一种方法优化这个过程呢；显然我们可以想到一开始取a[n/2]的值然后和k比较来更快的查找k元素。
//二分查找 递归
int k;
void InsertSortK (int a[],int n, int min, int max){
int j = (min + max)/2;
if(a[j] > k){
max = j;
InsertSortK(a[],n,min,max);
}else if(a[j]<k){
min = j;
InsertSortK(a[],n,min,max);
}else {
break;
}
}
//二分查找 循环
int min, max, mid;
int k;
min = 0;
max = n-1;
while (min <= max){
mid = (min+max)/2;
if(key < a[mid])
max = mid-1;
else if(key > a[mid])
min = mid+1;
else
k = a[mid];
}
二分插入排序是对直接插入排序的一种改进，它本质是在直接插入排序中从后向前扫描插入记录阶段（第二步）的优化，也就是对用二分查找替换直接查找方法。
算法思想：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[min]，末元素设置为a[max]，则轮比较时将待插入元素与a[k]，其中k=(min+max)/2相比较,如果比参考元素大，则选择a[min]到a[k-1]为新的插入区域(即max=k-1)，否则选择a[k+1]到a[max]为新的插入区域（即min=k+1），如此直至min<=max不成立，即将此位置之后所有元素后移一位，并将新元素插入a[max+1]。
void BinsertSort(int a[], int len)
{
int i, j;
int min, max, mid;
int key;
for(i = 1; i < len; i++){
key = a[i];
min = 1; max = i-1;
while (min <= max){
mid = (min+max)/2;
if(key < a[mid])
max = mid-1;
else
min = mid+1;
}
for(j = i-1; j >=max+1; --j)
a[j+1] = a[j];
a[max+1] = key;
}
}
希尔排序
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
本质上是对直接排序每次只移动一个元素的优化，希尔排序每次能排序n个元素；(n是子序列的个数)；
算法描述:1.先取序列个数d(d< n);把全部记录分为d组，然后在各个组内部排序;
2.然后取d1(d1<d)，重复分组排序操作,直到排序完毕;
| 序列 | 2 | 6 | 7 | 9 | 4 | 5 | 3 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| 分组(4) | 2a | 6b | 7c | 9d | 4 | 5a | 3b | 1c | 0d |
| 排序 | 2a | 3b | 1c | 0d | 4 | 5a | 6b | 7c | 9d |
| 分组(2) | 2a | 3b | 1a | 0b | 4 | 5a | 6b | 7a | 9b |
| 排序 | 1a | 0b | 2a | 3b | 4 | 5aa | 6b | 7a | 9b |
| 分组(1) | 1a | 0a | 2a | 3a | 4a | 5a | 6a | 7a | 9a |
| 排序 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
//直接插入排序算法 dk分组个数
void InsertSortdk(int a[],int n,int dk){
int j,temp;
for(int k=1;k<dk;k++){
for(int i=k+1;i<n;i+=dk){
temp = a[i];
for(j=i-1;j>=0;j--){
if(a[j]>temp)
a[j+1] = a[j];
else
break;
}
a[j+1]= temp;
}
}
}
//希尔排序算法
void ShellSort(int a[], int n)
{
int i, j, gap;
for(gap = n/2; gap>0; gap /= 2) //步长
ShellInsertSort(a, n, gap);
}
选择排序
顾名思义，选择排序的本质在于“选择”，那么选择什么呢？选择排序的基本思想是从待排序数组中选择出最大或者最小的一个记录，放在序列的起始位置，然后重复此过程。
简单选择排序
基本思想：从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推,达到排序的目的。
| 序列 | 9 | 3 | 7 | 8 | 5 | 2 | 1 | 0 | 选择数 |
|---|---|---|---|---|---|---|---|---|---|
| 第一次 | 0 | 3 | 7 | 8 | 5 | 2 | 1 | 9 | 0 |
| 第二次 | 0 | 1 | 7 | 8 | 5 | 2 | 3 | 9 | 1 |
| 第三次 | 0 | 1 | 2 | 8 | 5 | 7 | 3 | 9 | 2 |
| 第n次 | -- | -- | -- | -- | -- | -- | -- | -- | -- |
//从数组中找出最小的元素，返回其键值
int SelectMinKey(a[],int n ,int k){
int t = k;
int min = a[k];
for(int i=k;i<n;i++){
if(a[i]<min){
t=i;
min=a[i];
}
}
retur t;
}
//简单选择排序算法
void SelectSort(a[],int n){
for(int i=0;i<n;i++){
int k = SelectMinKey(a,n,i);
if(k != i){
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
二元选择排序
二元选择排序是对简单选择排序的优化，它本质是从数组两端分别进行最大和最小元素的简单选择排序。它只需要n/2次循环就可以完成数组的排序。
基本思想：从序列中找出最大的元素放在最后一个位置，找出最小一个元素放在第一个位置，n/2次循环后可以完成排序。
//从数组中找出最小的元素，返回其键值
int SelectMinKey(a[],int n ,int k){
int t = k;
int min = a[k];
for(int i=k;i<n;i++){
if(a[i]<min){
t=i;
min=a[i];
}
}
retur t;
}
//从数组中找出最大的元素，返回其键值
int SelectMaxKey(a[],int n ,int k){
int t = k;
int max = a[k];
for(int i=n;i>k;i--){
if(a[i]>max){
t=i;
max=a[i];
}
}
retur t;
}
//二元选择排序
void BinsertSelectSort(a[],int n){
int min=0;
int max = n-1;
for(int i=0;i<n/2;i++){
int k_min = SelectMinKey(a,n,i);
int k_max = SelectMaxKey(a,n,i);
min = i;
max = n-1-i;
if(k_min != min){
int temp = a[i];
a[i] = a[k_min];
a[k_min] = temp;
}
if(k_max != max){
int temp = a[max];
a[max] = a[k_max];
a[k_max] = temp;
}
}
}
实质上以上代码存在重复操作，在已选取好的序列中，从0-i，和n-i到n-i-1是不需要比较的
//二元选择排序
void BinsertSelectSort(int a[],int n) {
int i ,j , min ,max, tmp;
for (i=1 ;i <= n/2;i++) {
// 做不超过n/2趟选择排序
min = i; max = i ;
for (j= i+1; j<= n-i; j++) {
if (a[j] > a[max]) {
max = j ; continue ;
}
if (a[j]< a[min]) {
min = j ;
}
}
temp = a[i-1]; a[i-1] = a[min]; a[min] = temp;
temp = a[n-i]; a[n-i] = a[max]; a[max] = temp;
}
}
交换排序
交换排序的思想：通过重复交换两个次序相反的记录来达到排序的目的。冒泡排序和快速排序都属于交换排序的范畴。
冒泡排序
基本思想：冒泡排序通过比较相邻两个元素的大小，将两个元素正序，这样一次下来序列中最大的元素或者最小的元素会位于序列的两端，对剩下的元素进行重复操作，达到排序的目的。
基本方法(从小到大)：从左向右遍历数组，第一趟首先比较第一个元素和第二个元素的大小，小的放到前面，大的放在后面，然后继续比较第二个元素和第三个元素的大小，小的放到前面，大的放在后面......最终第一趟排序后将最大的元素确定在序列的最后面。重复此过程，将序列排序好。冒泡排序的本质上还是选择出一个最大的元素或者最小的元素到确定的位置来达到排序的目的。
//冒泡排序算法
void BubblingSort(int a[],int n){
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-j;j++){
if(a[j]>a[j+1]){
int temp = a[j] ;
a[j] = a[j+1] ;
a[j+1] = temp;
}
}
}
}
快速排序
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
方法:1.选择一个基准元素，
2.通过一趟排将大于基准元素的记录放在序列的右边，小于基准元素的记录放在序列的左边，这样一趟排序后基准元素将正好处在有序序列中它应该处于的位置。
3.分别对两部分记录重复第二部操作。
快速排序的本质是确定基准元素在序列中的位置。所有排序方法的本质是确定一个元素在序列中的位置。
void FastSort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
快速排序的时间复杂度：O(nlog2n)）
网友评论