数据结构排序算法总结
概述
排序有内部排序和外部排序，内部排序是数据纪录在内存中举行排序，而外部排序是因排序的数据很大，一次不能包容悉数的排序纪录，在排序历程当中须要接见外存。
1.插进去排序—直接插进去排序(Straight Insertion Sort)
基础思想:
将一个纪录插进去到已排序好的有序表中，从而获得一个新，纪录数增1的有序表。即：先将序列的第1个纪录算作是一个有序的子序列，然后从第2个纪录逐一举行插进去，直至全部序列有序为止。
要点：设立尖兵，作为暂时存储和推断数组边境之用。
假如遇见一个和插进去元素相称的，那末插进去元素把想插进去的元素放在相称元素的背面。所以，相称元素的前后递次没有转变，从原无序序列出去的递次就是排好序后的递次，所以插进去排序是稳固的。
算法的完成：
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插进去。小于的话，挪动有序表后插进去
int j= i-1;
int x = a[i]; //复制为尖兵，即存储待排序元素
a[i] = a[i-1]; //先后移一个元素
while(x < a[j]){ //查找在有序表的插进去位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插进去到正确位置
}
print(a,n,i); //打印每趟排序的效果
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
InsertSort(a,8);
print(a,8,8);
}
时候复杂度：O（n^2）.
其他的插进去排序有二分插进去排序，2-路插进去排序。
2. 插进去排序—希尔排序（Shell`s Sort）
希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的革新。希尔排序又叫削减增量排序
基础思想：
先将全部待排序的纪录序列支解成为多少子序列离别举行直接插进去排序，待全部序列中的纪录“基础有序”时，再对全部纪录举行顺次直接插进去排序。
操纵要领：
挑选一个增量序列t1，t2，…，tk，个中ti>tj，tk=1；按增量序列个数k，对序列举行k 趟排序；每趟排序，依据对应的增量ti，将待排序列支解成多少长度为m 的子序列，离别对各子表举行直接插进去排序。仅增量因子为1 时，全部序列作为一个表来处置惩罚，表长度即为全部序列的长度。
算法完成：
我们简朴处置惩罚增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数
即：先将要排序的一组纪录按某个增量d（n/2,n为要排序数的个数）分红多少组子序列，每组中纪录的下标相差d.对每组中悉数元素举行直接插进去排序，然后再用一个较小的增量（d/2）对它举行分组，在每组中再举行直接插进去排序。继承不断削减增量直至为1，末了运用直接插进去排序完成排序。
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 直接插进去排序的平常情势
*
* @param int dk 削减增量，假如是直接插进去排序，dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插进去。小于的话，挪动有序表后插进去
int j = i-dk;
int x = a[i]; //复制为尖兵，即存储待排序元素
a[i] = a[i-dk]; //起首后移一个元素
while(x < a[j]){ //查找在有序表的插进去位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插进去到正确位置
}
print(a, n,i );
}
}
/**
* 先按增量d（n/2,n为要排序数的个数举行希尔排序
*
*/
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
//ShellInsertSort(a,8,1); //直接插进去排序
shellSort(a,8); //希尔插进去排序
print(a,8,8);
}
希尔排序时效剖析很难，关键码的比较次数与纪录挪动次数依赖于增量因子序列d的拔取，特定状况下能够正确预算出关键码的比较次数和纪录的挪动次数。现在还没有人给出拔取最好的增量因子序列的要领。增量因子序列能够有种种取法，有取奇数的，也有取质数的，但须要注重：增量因子中除1 外没有公因子，且末了一个增量因子必需为1。希尔排序要领是一个不稳固的排序要领。
3. 挑选排序—简朴挑选排序（Simple Selection Sort）
基础思想：
在要排序的一组数中，选出最小（或许最大）的一个数与第1个位置的数交流；然后在剩下的数当中再找最小（或许最大）的与第2个位置的数交流，顺次类推，直到第n-1个元素（倒数第二个数）和第n个元素（末了一个数）比较为止。
操纵要领：
第一趟，从n 个纪录中找出关键码最小的纪录与第一个纪录交流；
第二趟，从第二个纪录最先的n-1 个纪录中再选出关键码最小的纪录与第二个纪录交流；
以此类推.....
第i 趟，则从第i 个纪录最先的n-i+1 个纪录当选出关键码最小的纪录与第i 个纪录交流，
直到全部序列按关键码有序。
算法完成：
void print(int a[], int n ,int i){
cout<<"第"<<i+1 <<"趟 : ";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 数组的最小值
*
* @return int 数组的键值
*/
int SelectMinKey(int a[], int n, int i)
{
int k = i;
for(int j=i+1 ;j< n; ++j) {
if(a[k] > a[j]) k = j;
}
return k;
}
/**
* 挑选排序
*
*/
void selectSort(int a[], int n){
int key, tmp;
for(int i = 0; i< n; ++i) {
key = SelectMinKey(a, n,i); //挑选最小的元素
if(key != i){
tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素交换
}
print(a, n , i);
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
cout<<"初始值：";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl<<endl;
selectSort(a, 8);
print(a,8,8);
}
简朴挑选排序的革新——二元挑选排序
简朴挑选排序，每趟轮回只能肯定一个元素排序后的定位。我们能够斟酌革新为每趟轮回肯定两个元素（当前趟最大和最小纪录）的位置,从而削减排序所需的轮回次数。革新后对n个数据举行排序，最多只需举行[n/2]趟轮回即可。细致完成以下：
void SelectSort(int r[],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 (r[j] > r[max]) {
max = j ; continue ;
}
if (r[j]< r[min]) {
min = j ;
}
}
//该交流操纵还可分状况议论以进步效力
tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;
}
}
4. 挑选排序—堆排序（Heap Sort）
堆排序是一种树形挑选排序，是对直接挑选排序的有用革新。
基础思想：
堆的定义以下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足
时称之为堆。由堆的定义能够看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完整二叉树，且一切非叶结点的值均不大于(或不小于)其后代的值，根结点（堆顶元素）的值是最小(或最大)的。如：
（a）大顶堆序列：（96, 83,27,38,11,09)
(b) 小顶堆序列：（12，36，24，85，47，30，53，91）
初始时把要排序的n个数的序列看做是一棵递次存储的二叉树（一维数组存储二叉树），调解它们的存储序，使之成为一个堆，将堆顶元素输出，获得n 个元素中最小(或最大)的元素，这时候堆的根节点的数最小（或许最大）。然后对前面(n-1)个元素从新调解使之成为堆，输出堆顶元素，获得n 个元素中次小(或次大)的元素。依此类推，直到只要两个节点的堆，并对它们作交流，末了获得有n个节点的有序序列。称这个历程为堆排序。
因而，完成堆排序需处理两个题目：
如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，如何调解盈余n-1 个元素，使其成为一个新堆。
起首议论第二个题目：输出堆顶元素后，对盈余n-1元素从新建成堆的调解历程。
调解小顶堆的要领：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（末了一个元素与堆顶举行交流），堆被损坏，其缘由仅是根结点不满足堆的性子。
2）将根结点与左、右子树中较小元素的举行交流。
3）若与左子树交流：假如左子树堆被损坏，即左子树的根结点不满足堆的性子，则重复要领 （2）.
4）若与右子树交流，假如右子树堆被损坏，即右子树的根结点不满足堆的性子。则重复要领 （2）.
5）继承对不满足堆性子的子树举行上述交流操纵，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调解历程为挑选。
再议论对n 个元素初始建堆的历程。
建堆要领：对初始序列建堆的历程，就是一个重复举行挑选的历程。
1）n 个结点的完整二叉树，则末了一个结点是第个结点的子树。
2）挑选从第个结点为根的子树最先，该子树成为堆。
3）以后向前顺次对各结点为根的子树举行挑选，使之成为堆，直到根结点。
算法的完成：
从算法形貌来看，堆排序须要两个历程，一是竖立堆，二是堆顶与堆的末了一个元素交流位置。所以堆排序有两个函数构成。一是建堆的渗入函数，二是重复挪用渗入函数完成排序的函数。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 已知H[s…m]除了H[s] 外均满足堆的定义
* 调解H[s],使其成为大顶堆.行将对第s个结点为根的子树挑选,
*
* @param H是待调解的堆数组
* @param s是待调解的数组元素的位置
* @param length是数组的长度
*
*/
void HeapAdjust(int H[],int s, int length)
{
int tmp = H[s];
int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调解结点的右孩子结点的位置)
while (child < length) {
if(child+1 <length && H[child]<H[child+1]) { // 假如右孩子大于左孩子(找到比当前待调解结点大的孩子结点)
++child ;
}
if(H[s]<H[child]) { // 假如较大的子结点大于父结点
H[s] = H[child]; // 那末把较大的子结点往上挪动，替代它的父结点
s = child; // 从新设置s ,即待调解的下一个结点的位置
child = 2*s+1;
} else { // 假如当前待调解结点大于它的摆布孩子，则不须要调解，直接退出
break;
}
H[s] = tmp; // 当前待调解的结点放到比其大的孩子结点位置上
}
print(H,length);
}
/**
* 初始堆举行调解
* 将H[0..length-1]建成堆
* 调解完以后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
//末了一个有孩子的节点的位置 i= (length -1) / 2
for (int i = (length -1) / 2 ; i >= 0; --i)
HeapAdjust(H,i,length);
}
/**
* 堆排序算法
*/
void HeapSort(int H[],int length)
{
//初始堆
BuildingHeap(H, length);
//从末了一个元素最先对序列举行调解
for (int i = length - 1; i > 0; --i)
{
//交流堆顶元素H[0]和堆中末了一个元素
int temp = H[i]; H[i] = H[0]; H[0] = temp;
//每次交流堆顶元素和堆中末了一个元素以后，都要对堆举行调解
HeapAdjust(H,0,i);
}
}
int main(){
int H[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值：";
print(H,10);
HeapSort(H,10);
//selectSort(a, 8);
cout<<"效果：";
print(H,10);
}
剖析:
设树深度为k，从根到叶的挑选，元素比较次数最多2(k-1)次，交流纪录最多k 次。所以，在建好堆后，排序历程当中的挑选次数不凌驾下式：
而建堆时的比较次数不凌驾4n 次，因而堆排序最坏状况下，时候复杂度也为：O(nlogn )。
5. 交流排序—冒泡排序（Bubble Sort）
基础思想：
在要排序的一组数中，对当前还未排好序的范围内的悉数数，自上而下对相邻的两个数顺次举行比较和调解，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发明它们的排序与排序请求相反时，就将它们交换。
算法的完成：
void bubbleSort(int a[], int n){
for(int i =0 ; i< n-1; ++i) {
for(int j = 0; j < n-i-1; ++j) {
if(a[j] > a[j+1])
{
int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
}
冒泡排序算法的革新
对冒泡排序罕见的革新要领是到场一标志性变量exchange，用于标志某一趟排序历程当中是不是有数据交流，假如举行某一趟排序时并没有举行数据交流，则申明数据已按请求分列好，可马上完毕排序，防止不必要的比较历程。
6. 交流排序—疾速排序（Quick Sort）
基础思想：
1）挑选一个基准元素,一般挑选第一个元素或许末了一个元素,
2）经由过程一趟排序讲待排序的纪录支解成自力的两部份，个中一部份纪录的元素值均比基准元素值小。另一部份纪录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后离别对这两部份纪任命一样的要领继承举行排序，直到全部序列有序。
算法的完成：
递归完成：
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基准元素
while(low < high){ //从表的两头交替地向中心扫描
while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜刮，最多到low+1 位置。将比基准元素小的交流到低端
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
print(a,10);
return low;
}
void quickSort(int a[], int low, int high){
if(low < high){
int privotLoc = partition(a, low, high); //将表一分为二
quickSort(a, low, privotLoc -1); //递归对低子表递归排序
quickSort(a, privotLoc + 1, high); //递归对高子表递归排序
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值：";
print(a,10);
quickSort(a,0,9);
cout<<"效果：";
print(a,10);
}
剖析：
疾速排序是一般被以为在同数量级（O(nlog2n)）的排序要领中均匀机能最好的。但若初始序列按关键码有序或基础有序时，快排序反而蜕化为冒泡排序。为革新之，一般以“三者取中法”来拔取基准纪录，行将排序区间的两个端点与中点三个纪录关键码居中的调解为支点纪录。疾速排序是一个不稳固的排序要领。
7. 兼并排序（Merge Sort）
基础思想：
兼并（Merge）排序法是将两个（或两个以上）有序表兼并成一个新的有序表，即把待排序序列分为多少个子序列，每一个子序列是有序的。然后再把有序子序列兼并为团体有序序列。
兼并要领：
设r[i…n]由两个有序子表r[i…m]和r[m+1…n]构成，两个子表长度离别为n-i +1、n-m。
j=m+1；k=i；i=i; //置两个子表的肇端下标及辅佐数组的肇端下标若i>m 或j>n，转⑷ //个中一个子表已兼并完，比较拔取完毕//拔取r[i]和r[j]较小的存入辅佐数组rf
假如r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
不然，rf[k]=r[j]； j++； k++； 转⑵//将还没有处置惩罚完的子表中元素存入rf
假如i<=m，将r[i…m]存入rf[k…n] //前一子表非空
假如j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空兼并完毕。
//将r[i…m]和r[m +1 …n]兼并到辅佐数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
}
兼并的迭代算法
1 个元素的表老是有序的。所以对n 个元素的待排序列，每一个元素可算作1 个有序子表。对子表两两兼并生成n/2个子表，所得子表除末了一个子表长度可能为1 外，其他子表长度均为2。再举行两两兼并，直到生成n 个元素按关键码有序的表。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
//将r[i…m]和r[m +1 …n]兼并到辅佐数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
print(rf,n+1);
}
void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
int len = 1;
ElemType *q = r ;
ElemType *tmp ;
while(len < lenght) {
int s = len;
len = 2 * s ;
int i = 0;
while(i+ len <lenght){
Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表兼并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表兼并
}
tmp = q; q = rf; rf = tmp; //交流q,rf，以保证下一趟兼并时，仍从q 兼并到rf
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
int b[10];
MergeSort(a, b, 10);
print(b,10);
cout<<"效果：";
print(a,10);
}
两路兼并的递归算法
void MSort(ElemType *r, ElemType *rf,int s, int t)
{
ElemType *rf2;
if(s==t) r[s] = rf[s];
else
{
int m=(s+t)/2; /*中分*p 表*/
MSort(r, rf2, s, m); /*递归地将p[s…m]兼并为有序的p2[s…m]*/
MSort(r, rf2, m+1, t); /*递归地将p[m+1…t]兼并为有序的p2[m+1…t]*/
Merge(rf2, rf, s, m+1,t); /*将p2[s…m]和p2[m+1…t]兼并到p1[s…t]*/
}
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{ /*对递次表*p 作兼并排序*/
MSort(r, rf,0, n-1);
}
更多PHP相干学问，请接见ki4网！
以上就是数据结构排序算法总结的细致内容，更多请关注ki4网别的相干文章！
