算法基础===》==》=》排序（内部排）

一些最基本的排序算法：

* 插入排序
* 交换排序
* 选择排序
@ 插入排序：

1-直接插入排序：

* 从前端插入
* 从后端插入
2-希尔（Shell）排序

1-直接插入排序：

* 从前端插入： int arr[]={999,1,2,5,8,4,3,9,7};//"999"是一个容储器(arr[0]是一个监视哨),不参与排序。
void InsertSort(int n) { int i,j; for(i=2;i<=n;i++)//进行n-1次排序 { arr[0]=arr[i];
//设置监视哨---减少扫描量，提高效率。 j=i-1;//j代表有序序列的最后一个元素 while(arr[0]<arr[j]) { arr[j+1]=arr
[j];//记录后移 j--; } arr[j+1]=arr[0];//把存放在arr[0]中的原记录插入到正确位置 } }
* 从后端插入： int arr[]={0,1,2,5,8,4,3,9,7,999};
//"999"是一个容储器(arr[n+1]是一个监视哨),"0"是填补i=0的空白位置,"999"与"0"均不参与排序。 void InsertSort(
int n)//从第n-1个元素开始向它前面插入，直到第一个元素插入为止。 { int i,j; for(i=n-1;i>=1;i--)//进行n-1次排序 {
arr[n+1]=arr[i];//设置监视哨 j=i+1;//j代表有序序列的最后一个元素 while(arr[n+1]>arr[j]) { arr[j-1
]=arr[j];//记录前移 j++; } arr[j-1]=arr[n+1];//把存放在arr[n+1]中的原记录插入到正确位置 } }
2-希尔（Shell）排序==>直接插入排序的改进版
void InsertSort(int n) { int i,j,d; for(d=n/2;d>=1;d=d/2)//进行n-1次排序 { for(i=d+1
;i<=n;i++) { arr[0]=arr[i];//设置监视哨 j=i-d;//前后位置的增量为d,而不是1 while(j>0&&arr[0]<arr[
j]) { arr[j+d]=arr[j];//记录后移，查找插入位置 j=j-d; } arr[j+d]=arr[0];//插入 } } }
------》源代码：
#include<iostream> using namespace std; //1.数组的初始化： int arr[]={999,1,2,5,8,4,3,
9,7};//"999"是一个容储器(arr[0]是一个监视哨),不参与排序。 //2.希尔排序： void InsertSort(int n) { int i
,j,d; for(d=n/2;d>=1;d=d/2)//进行n-1次排序 { for(i=d+1;i<=n;i++) { arr[0]=arr[i];
//设置监视哨 j=i-d;//前后位置的增量为d,而不是1 while(j>0&&arr[0]<arr[j]) { arr[j+d]=arr[j];
//记录后移，查找插入位置 j=j-d; } arr[j+d]=arr[0];//插入 } } } void Show_arr(int n) { int i;
for(i=1;i<=n;i++) cout<<arr[i]<<'\t'; cout<<endl; } void main() { InsertSort(8);
Show_arr(8); }
直接插入排序的算法的时间复杂度为O(n^2)，直接插入排序是一种稳定的排序方法。而shell_sort的算法的时间复杂度为O(n* log2^n)~ O（n
^2） 大略为O(n^(3/2)),shell_sort不是一种稳定的排序方法

@交换排序：

* 冒泡排序
* 快速排序
1- 冒泡排序：
void Bubble_Sort(int *a,int n) { int i, j, t; for(i=0;i<n-1;i++) { for(j=0;j<n-
i-1;j++) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } }
2-快速排序:
void Quick_Sort(int low,int high) { if(low>=high) return ; int i=low,j=high;
//避免引起歧义 arr[0]=arr[low]; while(i<j) { while(i<j&&arr[0]<=arr[j])
//"i<j"绝对不能省,此处与外循环的含义不同 j--; arr[i]=arr[j]; while(i<j&&arr[i]<=arr[0]) i++; arr
[j]=arr[i]; } arr[i]=arr[0]; Quick_Sort(low,i-1); Quick_Sort(i+1,high); }
------》源代码：
#include<iostream> using namespace std; //1.数组的初始化： int arr[]={0,1,2,5,8,4,3,9,
7}; //2.快速排序：一个形象的比喻-》“选取一个中间点，两边互相扔石头” void Quick_Sort(int low,int high) { if(
low>=high) return ; int i=low,j=high;//避免引起歧义 arr[0]=arr[low]; while(i<j) {
while(i<j&&arr[0]<=arr[j])//"i<j"绝对不能省,此处与外循环的含义不同 j--; arr[i]=arr[j]; while(i<j
&&arr[i]<=arr[0]) i++; arr[j]=arr[i]; } arr[i]=arr[0]; Quick_Sort(low,i-1);
//这里采用递归来化简算法的难度 Quick_Sort(i+1,high); } void Show_arr(int n) { int i; for(i=1;i
<=n;i++) cout<<arr[i]<<'\t'; cout<<endl; } void main() { Quick_Sort(1,8);
Show_arr(8); }
冒泡排序的算法的时间复杂度为O(n^2)，是一种稳定的排序方法。
快速排序的算法的时间复杂度为O(n* log2^n)~ O（n ^2），不是一种稳定的排序方法。

@选择排序:

* 直接选择排序
* 堆排序
直接选择排序：
void Sort(int *a,int len) { int i,j,min,t; for(i=0;i<len-1;i++) { for(min=i,j=i
+1;j<len;j++) if(a[min]>a[j]) { min=j; } if(min!=i) { t=a[i]; a[i]=a[min]; a[min
]=t; } } }
------》源代码：
#include<iostream> using namespace std; //1.数组的初始化： int arr[]={1,2,5,8,4,3,9,7}
; //2.选择排序： void Sort(int *a,int len) { int i,j,min,t; for(i=0;i<len-1;i++) {
for(min=i,j=i+1;j<len;j++) if(a[min]>a[j]) { min=j; } if(min!=i) { t=a[i]; a[i]=
a[min]; a[min]=t; } } } void Show_arr(int n) { int i; for(i=0;i<n;i++) cout<<arr
[i]<<'\t'; cout<<endl; } void main() { Sort(arr,8); Show_arr(8); }
堆排序：==>选择排序的改进版
*什么是堆？—
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的数值或索引总是小于（或者大于）它的父节点。
堆排序的生成及其排序原理：



堆排序的实现：
void Adjust(int i,int n)//i代表待调整元素的下标，n代表最后一元素的下标。 { int j; arr[0]=arr[i];
while(i<n&&2*i<=n) { j=2*i;//j为i左孩子下标 if(j<n&&arr[j]>arr[j+1]) j++;//j指向较小的孩子 if
(arr[0]>arr[j]) { arr[i]=arr[j]; i=j; } else break; } arr[i]=arr[0]; } void
Build_Heap(int n) { int i; for(i=n/2;i>0;i--) Adjust(i,n); } void Show_arr(int n
) { int i; for(i=1;i<=n;i++) cout<<arr[i]<<'\t'; cout<<endl; } void Heap_Sort(
int n) { int i,t; Build_Heap(n); cout<<"初始堆积树："<<endl; Show_arr(8); cout<<endl;
for(i=n;i>1;i--) { t=arr[1]; arr[1]=arr[i]; arr[i]=t; cout<<endl<<"第 "<<n-i+1<<
"趟："<<endl; Show_arr(8); Adjust(1,i-1); } }
------》源代码：
#include<iostream> using namespace std; //1.数组的初始化： int arr[]={0,1,2,5,8,4,3,9,
7}; /*2.堆积树的调整过程： 从二叉树的叶子节点处往上逐一比较来建立最大堆积树：*/ void Adjust(int i,int n)
//i代表待调整元素的下标，n代表最后一元素的下标。 { int j; arr[0]=arr[i]; while(i<n&&2*i<=n) { j=2*i;
//j为i左孩子下标 if(j<n&&arr[j]>arr[j+1]) j++;//j指向较小的孩子 if(arr[0]>arr[j]) { arr[i]=
arr[j]; i=j; } else break; } arr[i]=arr[0]; } //3.堆积树的建立： void Build_Heap(int n)
{ int i; for(i=n/2;i>0;i--) Adjust(i,n); } //显示： void Show_arr(int n) { int i;
for(i=1;i<=n;i++) cout<<arr[i]<<'\t'; cout<<endl; } //4.堆积排序： void Heap_Sort(int
n) { int i,t; Build_Heap(n); cout<<"初始堆积树："<<endl; Show_arr(8); cout<<endl; for
(i=n;i>1;i--) { t=arr[1]; arr[1]=arr[i]; arr[i]=t; cout<<endl<<"第 "<<n-i+1<<"趟："
<<endl; Show_arr(8); Adjust(1,i-1); } } void main() { Show_arr(8); cout<<endl;
Heap_Sort(8); }

直接选择排序的算法的时间复杂度为O(n^2)，由于直接选择排序交换次数少，当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。但它却并不是一种稳定的排序方法,综合来看其性价比
较低.
堆排序方法对记录数较小的排序效果并不理想，但对于n较大的文件很有意义，因为其运行时间主要建立在初始建堆和反复调整堆上。
建堆的时间复杂度与堆所对应的完全二叉树的深度的数量级log2^n 有关，而调用数量级为n,所以整个堆排序的时间复杂度为O(n*
log2^n)。在空间复杂度方面，堆排序只需要一个辅助空间，为O(1)。此外，堆排序并不是稳定的排序哦。

*ps:在算法的设计中排序的方法有很多种，但具体情况还需要具体分析，在情景中应当采取最合适的排序算法。

• « 上一篇：ML.NET技术研究系列1-入门篇
• » 下一篇：MySQL中一条SQL语句的执行过程