基础排序算法

基础排序算法

七个基础排序算法（均为内部排序）： 直接插入排序 希尔排序 冒泡排序 简单选择排序 快速排序 堆排序 二路归并排序

排序算法稳定性：经过排序后，具有相同关键码的元素之间的相对次序保持不变，则称该排序方法是稳定的;否则不稳定。

直接插入排序：

void InsertSort(int a[],int n){ // index start at 1, a[0] is temp one int i,j; for(i=2;i<=n;i++){ if(a[i]a[0];j--){ a[j+1]=a[j]; } a[j+1]=a[0];

直接插入排序是一种稳定的排序，时间复杂度O(n^2)，空间复杂度是O(1)

希尔排序：

按增量将元素分成不同的子集，对子集不断的进行插入排序。

void ShellSort(int a[],int n){ // index start at 1, a[0] is temp one int d,i,j,k; for(d=n/2;d>=1;d>>=1){ for(i=d+1;i<=n;i++){ // InsertSort if(a[i]0&&a[0]

如果a[i]>a[i-d]始终成立，那么时间是O(nlogn), 但是在糟糕的情况下是O(n^2)。空间复杂度是O(1) 希尔排序是一种不稳定的排序方法

冒泡排序：

相邻元素如果反序两两交换，直到所有的位置统统确定下来。

void BubbleSort(int a[],int n){ // index start at 1, a[0] is temp one int i,j,k; for(i=1;i<=n;i++){ for(j=1;j<=n-i;j++){ if(a[j]>a[j+1]) { a[j]=a[j]^a[j+1]; a[j+1]=a[j]^a[j+1]; a[j]=a[j]^a[j+1]; } } }}

这是稳定的排序方法，时间复杂度：O(n^2)

快速排序：

选择一个轴值，使得左边的元素的值小于它，右边的元素的值大于它。对于产生的分区重复上诉过程。该算法是对冒泡排序的改进。

int partion(int a[],int start,int end){ int i=start,j=end; int temp=a[start]; while(i=temp) j--; a[i]=a[j]; // i are more while(i

快速排序不是一种稳定的排序算法。平均来说，Qsort的时间复杂度是O(nlogn)

简单选择排序：

思想：第i趟将待排序记录r[i……n]中最小的元素和r[i]交换

void SelectSort(int a[],int n){ for(int i=1;ia[j]) dex=j; // use the index to compare and find min one } if(dex!=i) { a[dex]=a[dex]^a[i]; a[i]=a[dex]^a[i]; a[dex]=a[dex]^a[i]; } }}

堆排序：

堆分为大根堆和小根堆。父节点比左右孩子大或者小。

维护堆的性质：

堆排序思路：先建堆，自下而上建堆。然后将根节点取出并输出，再把最后的元素放在根节点上，维护堆。重复上面的过程。

void Sift(int a[],int s,int n){ int i=s,j=2*s; while(j<=n) { //if(ja[j+1]) j=j+1; // small heap get big --> small //if(a[i]<=a[j]) break; if(j big if(a[i]>=a[j]) break; else { swap(a[i],a[j]); i=j; j=2*j; } }}void HeapSort(int a[],int s,int n){ for(int i=n/2;i>=1;i--) Sift(a,i,n); // 建堆自下而上 show(a,n); for(int i=n;i>1;i--){ swap(a[1],a[i]); Sift(a,1,i-1);

堆排序的时间复杂度为O(nlogn)，是不稳定的排序算法

二路归并排序：

最开始是相邻元素排序，递归进行，比较相邻子集的序列，最后完成进行排序。

const int N=1e3;int b[N];void merge(int a[],int sdex,int mdex,int edex){ int i=sdex,j=mdex+1,k=sdex; while(i<=mdex&&j<=edex){ if(a[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。