这篇文章总结了一些常用的排序算法，如有错误，还望指正。 分类 1）插入排序（直接插入排序、希尔排序） 2）交换排序（冒泡排序、快速排序） 3）选择排序（直接选择排序、堆排序） 4）归并排序 5）线性时间排序（计数排序、基数排序、桶排序） 直接插入排序 基本思想：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。时间复杂度为O(n^2)，空间复杂度为O(1),是稳定排序。 冒泡排序 基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。时间复杂度为O(n^2)，空间复杂度为O(1),是稳定排序。 直接选择排序 基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。时间复杂度为O(n^2)，空间复杂度为O(1),为不稳定排序。 快速排序 快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动
该方法的基本思想是： 1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 四种排序算法代码如下所示*
/* main.cpp * BubbleSort * Created by hry on 16-9-9 * @算法导论 */ #include <iostream> #include <stdio.h> using namespace std; void InsertSort(int a[],int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; for(j=i-1;j>=0 &&a[j]>temp;j--){ a[j+1]=a[j]; } a[j+1]=temp; } } void BubbleSort(int a[],int n) { int i,j,temp,flag=0; for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { if(a[i]>a[j]) { flag=1; temp=a[j]; a[j]=a[i]; a[i]=temp; } } if(flag==0) //一趟比较后若没有任何数发生交换，则退出 break; } } void ChooseSort(int a[],int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) { if(a[k]>a[j]) k=j; } temp=a[k]; a[k]=a[i]; a[i]=temp; } } int partition(int a[],int low,int high) { int pivotloc=a[low],l=low; while(low<high) { while(low<high && pivotloc<= a[high]) {high--;} a[low]=a[high]; while(low<high && pivotloc>=a[low]) {low++;} a[high]=a[low]; } a[low]=pivotloc; return low; } void QuickSort(int a[],int low,int high) { int pivotloc; if(low<high) { pivotloc=partition(a,low,high); QuickSort(a,low,pivotloc-1); QuickSort(a,pivotloc+1,high); } } int main() { int n; cout<<"Please intput the number of the values:"; cin>>n; int *a=(int *)malloc(n*sizeof(int)); for(int i=0;i<n;i++) cin>>a[i]; //BubbleSort(a,n); //冒泡排序 //InsertSort(a,n); //插入排序 //ChooseSort(a,n); //选择排序 //QuickSort(a,0,n-1); // HeapSort(a,n); cout<<"Output the result of the values"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; free(a); return 0; }堆排序 堆排序的思想参考博客：http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/ C++代码为：
void HeapSort(int a[],int i,int n) { int temp; int LeftChild=2*i+1; int RightChild=2*i+2; int root=i; if(LeftChild<n&&a[LeftChild]>a[root]) root=LeftChild; if(RightChild<n&&a[RightChild]>a[root]) root=RightChild; if(root!=i) { temp=a[root]; a[root]=a[i]; a[i]=temp; HeapSort(a,root,n); } } #include <iostream> #include <stdio.h> using namespace std; int main() { int n; cout<<"Please intput the number of the values:"; cin>>n; int *a=(int *)malloc(n*sizeof(int)); for(int i=0;i<n;i++) cin>>a[i]; for(int i=n/2;i>=0;i--) HeapSort(a,i,n); //建堆（大根堆） for(int j=n-1;j>=0;j--)//堆排序 { int temp=a[j]; a[j]=a[0]; a[0]=temp; for(int i=j/2;i>=0;i--) HeapSort(a,i,j); } cout<<"Output the result of the values"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; free(a); return 0; }归并排序 归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8，1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4+4=11,； 逆序数为14；
算法描述 归并操作的工作原理如下： 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 归并排序是稳定的排序.即相等的元素的顺序不会改变.速度仅次于快速排序. C++代码为：
#include <iostream> #include <stdio.h> using namespace std; int Merge(int *a,int low,int mid,int high) { int i,j,index=low,count=0; int *b=(int *)malloc(sizeof(int)*(mid+1)); int *c=(int *)malloc(sizeof(int)*(high-mid)); int num1=mid-low+1; int num2=high-mid; for(i=0;i<num1;i++) { b[i]=a[low+i]; cout<<b[i]<<" "; } for(i=0;i<num2;i++) { c[i]=a[mid+1+i]; } i=0; j=0; while(i<num1 && j<num2) { if(b[i]>c[j]) { a[index]=c[j]; j++; index++; count+=(j+1-low); // count+=(num1-i); } else { a[index]=b[i]; i++;; index++; } } while(i<num1) { a[index]=b[i]; i++; index++; } while(j<num2) { a[index]=c[j]; index++; j++; } free(b); free(c); return count; } int MergeSort(int *a,int low,int high) { int count=0; if(low<high) { int mid=(low+high)/2; count+= MergeSort(a,low,mid); count+=MergeSort(a,mid+1,high); count+=Merge(a,low,mid,high); } return count; } #include <iostream> #include <stdio.h> using namespace std; int main() { int n,count; cout<<"Please intput the number of the values:"; cin>>n; int *a=(int *)malloc(n*sizeof(int)); for(int i=0;i<n;i++) cin>>a[i]; count=MergeSort(a,0,n-1); cout<<"Output the result of the values"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; cout<<"count:"<<count; free(a); return 0; }http://blog.csdn.net/liuchen1206/article/details/6954074
