前言

排序，三大查找是《数据结构》当中十分根底的知识点，在这里为了温习顺带总结了一下常见的排序算法。

罕用比拟排序算法的性能：

一、插入排序

根本思维：在一个曾经排好序的序列中，将未被排序的元素依照原先序列的排序规定插入到序列中的指定地位。

罕用举例：间接插入排序

间接插入排序（Straight Insertion Sorting）是一种简略的排序算法，他的根本思维是顺次将每个记录插入到一个曾经排好序的有序表中去，从而失去一个新的、记录减少1的有序表。具体过程如下：

初始序列：{45 38 66 90 88 10 25 }

第一步对前两个数进行排序，把38插入到45之前，失去新的序列{45 38 66 90 88 10 25}

第二步对前三个数进行排序，把66插入到有序序列{45 38}的适合地位，即{45 38 66 90 88 10 25}

当前的步骤是在都是在以上根底上的一个递归过程晓得最初一个数25插入到适合的地位失去最终序列{10 25 38 45 66 88 90}

算法形容：

<span style="font-family:KaiTi_GB2312;font-size:18px;">void StraightInsertSort(List R,int n) //对程序表R进行间接插入排序 { int i, j; for (i=2;i<=n;i++)//n为表长，从第二个记录起进行插入 { R[0] = R[i];//第i个记录复制为岗哨 j = i - 1; while (R[0].key<R[j].key)//与岗哨比拟，直至键值不大于岗哨值 { R[j +1]=R[j];//将第j个记录赋值给第j+1个记录 j--; } R[j + 1] = R[0];//将第i个记录插入的序列中 } }</span>

二、替换排序

根本思维：比拟两个记录的键值大小，如果两个记录键值的大小呈现逆序，则替换这两个记录，这样将键值较小的记录向序列前部挪动，键值较大的记录向序列后部挪动，最终将失去有序序列。

（1）冒泡排序

冒泡排序法（Bubble Sorting）首先将第一个记录的键值和第二个记录的键值进行比拟，若为逆序则将这两个记录替换，而后持续比拟第二个和第三个记录的键值。以此类推，直到实现第n-1个记录和第n个记录的键值比拟替换为止。这时便实现了第一趟气泡，其后果是将最大的记录移到最初一位。而后第二次气泡跟第一次相似，其后果是将第二大的记录移到倒数第二位。反复以上过程，直到整个排序过程终止失去最终有序序列。

<span style="font-family:KaiTi_GB2312;font-size:18px;">  void BubbletSort(List R,int n) { int i, j,temp,endsort; for (i=1;i<=n-1;i++) { endsort = 0; for (j = 1; j <= n - i - 1; j++) { if (R[j].key>R[j+1].key)//若为逆序则替换记录 { temp = R[j]; R[j] = R[j + 1]; R[j + 1] = temp; endsort = 1; } } if (endsort == 0) break; } }</span>### （2）疾速排序

疾速排序（Quick Sorting）是对冒泡排序的一种改良。它的根本思维是在n个记录中取某一个记录的键值为规范，通常取第一个记录键值为基准，通过一趟排序将待排序的记录分为小于等于这个键值和大于这个键值的两个独立的局部，这时后面局部的记录键值均比前面的记录键值小，而后对这两局部别离依照这种办法排序，直到取得整个有序序列。

算法形容：

<span style="font-family:KaiTi_GB2312;font-size:18px;">//第一趟疾速排序算法 int QuickPartition(List R,int low,int hign) { x=R[low]//赋初值，规范数 while (low < hign) { while ((low <hign) && (R[hign].key>=x.key )) hign--; R[low]=R[hign];//自尾端进行比拟，将比x小的记录移到低端 while ((low <hign) && (R[low].key<=x.key )) low++; R[hign]=R[low];//自首端进行比拟，将比x大的记录移到高端 } R[low]=x;//第一趟排序完结，将x移到其最终地位 return low ; }</span>

三、抉择排序

根本思维：每次在n-i+1（i=1,2,3……，n-1）个记录中选取键值最小的记录作为有序序列的第i个记录。

罕用举例：间接抉择排序、堆排序。

（1）间接抉择排序

间接抉择排序（Selection Sorting）的根本思维是在第i次抉择操作中，通过n-i次键值比拟，从n-i+1个记录中选出最小的记录，并和第i(1<=i<=n-1)个记录替换。

算法形容：

<span style="font-family:KaiTi_GB2312;font-size:18px;">        void SelectSort(List R,int n) { int min, i, j; for(i=1;i<=n-1;i++)//每次循环抉择出最小一个键值 { min=i;//假如第i个记录键值最小 for(j=i+1;j<=n;j++) { if(R[j].key<R[min].key) min =j;//记录下键值最小记录的下标 if(min!=i) swap(R[min],R[i]);//将最小键值记录和第i个记录替换 } } }</span>

（2）堆排序

堆排序（Heap Sorting）是利用堆的数据结构所设计的一种排序算法，可利用数组的特点疾速定位指定索引的元素。堆分为最大堆和最小堆，最大堆中的任一节点的值都不小于它的两个孩子的值（若存在孩子的话）；最小堆则任一节点的值都不大于它的两个孩子的值。

算法形容：

<span style="font-family:KaiTi_GB2312;font-size:18px;">void Sift(List R,int k,int m) { int i, j, x; List t; i = k; j = 2 * i; x = R[k].key; t = R[k]; while (j<=m) { if ((j < m) && (R[j].key > R[j + 1].key)) j++;//若存在右子树且右子树的关键字小，则沿右分支筛选 if (x < R[j].key) break;//筛选结束 else { R[i] = R[j]; i = j; j = 2 * i; } R[i] = t;//填入适当地位 } } //堆排序算法 void HeapSort(List R) { int i; for (i = n / 2; i >= 1; i--) Shit(R, i, n);//从第n/2个记录开始进行筛选建堆 for (i=n;i>=2;i--) { swap(R[1], R[i]);//将堆顶记录和堆中最初一个记录调换 Sift(R, 1, i - 1);//调整R[1]使R[1],……,R[i-1]变成堆 } }</span>

四、归并排序

根本思维：

1）将曾经有序的子序列合并，失去齐全有序的序列，

2）先使每个子序列有序，再使子序列段间有序

3）若将两个有序表合并成一个有序表称为二路归并

常见举例：

二路归并排序。

二路归并排序是将两个有序表联合成一个有序表，根本思维是假如序列中有n个记录，可看成是n个有序的子序列，每个序列的长度为1.首先将每相邻的两个记录合并，失去n/2（向上取整）个较大的有序序列，每个子序列蕴含2个记录，再将上述子序列两两合并，失去（n/2）/2（向上取整）个有序序列，如此重复，晓得失去最终有序序列为止。

步骤：

a 申请空间，让他大小为两个曾经排序的序列之和，

该空间用来寄存合并后的序列

b 设定两个指针，最后地位别离为两个曾经排序序列起始地位

c 比拟两个指针所指向的元素，抉择绝对较小的放入合并空间，并挪动

指针到下一个地位

d 反复步骤c 晓得某个指针达到序列尾

e 将另一个序列剩下的所有元素间接复制到合并序列尾。

//归并排序void Merge(int a[], int left, int mid,int right){ int size = right - left + 1; int *temp = (int *)malloc(size*sizeof(int)); int i = left; int j = mid + 1; int index = 0; while (i <= mid && j <= right) { temp[index++] = a[i] < a[j] ? a[i++] : a[j++]; } while (i <= mid) { temp[index++] = a[i++]; } while (j <= right) { temp[index++] = a[j++]; } for (int k = 0; k < size; k++) { a[left++] = temp[k]; }}void MergeSort(int a[], int left, int right){ if (left == right) return; int mid = left + ((right - left) >> 1); MergeSort(a, left, mid); MergeSort(a, mid + 1, right); Merge(a, left, mid, right);}

五.基数排序

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“调配”与“收集”来实现排序。

调配：咱们将L[i]中的元素取出，首先确定其个位上的数字，依据该数字调配到与之序号雷同的桶中

收集：当序列中所有的元素都调配到对应的桶中，再依照程序顺次将桶中的元素收集造成新的一个待排序列L[ ]

对新造成的序列L[]反复执行调配和收集元素中的十位、百位...直到调配完该序列中的最高位，则排序完结

看到这里属实不容易了，点亮小心心喔~