转载请标明出处：http://i.cnblogs.com/EditPosts.aspx?postid=4711012&update=1
1.直接插入排序
思想：待排序记录R[1...n]看成两段，有序R[1...m],无序R[m+1,n],每次将无序记录插到有序记录中，直到整体有序。
// InsertSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<iostream> #include <vector> #include <iterator> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void insert_sort(int a[],int n) { int i,j,temp; for (i=1;i<n;i++) { temp=a[i]; for (j=i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); insert_sort(a,9); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
2.shell排序
思想：按增量d分组排序，d每次减半，直至1
// shell_sort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void shell_sort(int a[],int n) { int d,i,j,temp; for (d=n/2;d>0;d=d/2)//增量控制 { for(i=d;i<n;i++)//插入排序类似 { temp=a[i]; for (j=i-d;(j>=0&&a[j]>temp);j-=d) { a[j+d]=a[j]; } a[j+d] = temp; } } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); shell_sort(a,9); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
看成改进后的插入排序
3.冒泡排序
思想：每两个一比较，n个元素比较n-1次，得到一个目标元素
// bubble_sort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void bubble_sort(int a[],int n) { int i=0; int j=0; int temp=0; int exchange=0; for (i=0;i<n-1;i++)//n-1趟 { for (j=0;j<n-i-1;j++) { if (a[j+1]<a[j]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; exchange = 1; } } if (exchange!=1)//没有交换，进行下一次扫描 { return; } } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); bubble_sort(a,9); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
4.快速排序
思想：选取第一个元素为基准，通过一趟排序将序列分为大小两部分，此时正好得到基准的正确位置。再以此对左右两部分递归划分
从右找第一个小于pivot的元素，交换；再从左找第一个大于pivot的元素，交换。。。
// bubble_sort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void quick_sort(int a[],int low,int high) { int i,j,pivot; if (low<high) { i=low; j=high; pivot=a[low]; while(i<j) { while (i<j && a[j]>=pivot)--j; if(i<j) { a[i]=a[j]; i++; } //a[i++]=a[j]; while(i<j&&a[i]<pivot)++i; if (i<j)a[j--]=a[i]; } a[i]=pivot; quick_sort(a,low,i-1); quick_sort(a,i+1,high); } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); quick_sort(a,0,8); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
// bubble_sort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } int getMiddle(int a[],int low,int high) { int i=low; int j=high; int pivot=a[low]; while(i<j) { while (i<j && a[j]>=pivot)--j; if(i<j) { a[i]=a[j]; i++; } //a[i++]=a[j]; while(i<j&&a[i]<pivot)++i; if (i<j)a[j--]=a[i]; } return i; } void quick_sort(int a[],int low,int high) { if (low<high) { int middle=getMiddle(a,low,high); quick_sort(a,low,middle-1); quick_sort(a,middle+1,high); } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); quick_sort(a,0,8); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
// quicksort.cpp : 定义控制台应用程序的入口点。 /* 以上给出的是最初的版本，该程序为算法导论给出的原址排序 */ #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int size) { for (int i=0;i<size;i++) { cout<<a[i]<<" "; } cout<<endl; } void exchange(int &a,int &b) { int temp=a; a=b; b=temp; } int partition(int a[],int p,int r) { int x=a[r]; int i=p-1; int j; for (j=p;j<=r-1;j++) { if(a[j]<x) { i++; exchange(a[j],a[i]); } } exchange(a[i+1],a[r]); return i; } void quicksort(int a[],int low,int high) { int pos; if (low<high) { pos=partition(a,low,high); quicksort(a,low,pos); quicksort(a,pos+1,high); } } int _tmain(int argc, _TCHAR* argv[]) { int a[]={5,3,6,7,9,8,1,4,2}; cout<<"before:"<<endl; print(a,9); quicksort(a,0,8); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
5.选择排序
思想：在要排序的序列中选出最小的一个与第一个交换，然后在剩下的选出次小的与第二个交换，以此类推。
// bubble_sort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void select_sort(int a[],int n) { int minValue,index; for (int i=0;i<n;i++)//n-1次遍历 { minValue=a[i]; index=i; for (int j=i;j<n;j++) { if (a[j]<minValue)//保存每次遍历的最小数和下标 { minValue=a[j]; index=j; } } a[index]=a[i];//把最小值和a[i]交换 a[i]=minValue; } } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); select_sort(a,9); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
6.堆排序
思想：将R[1...n]看成是一棵完全二叉树的顺序存储结构，则：
1).将原始序列建成大(小)根堆；
2).将根与最后一个节点交换，输出根节点；
3).将2得到的二叉树调整为大根堆；
重复2),3);
/// bubble_sort.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> using namespace std; int heapsize = 0; int Left(int index){return (index<<1)+1;} //2i+1 int Right(int index){return (index<<1)+2;}//2i+2 void swap(int *a,int *b) { int t; t = *a; *a= *b; *a= t; } void print(int a[],int n) { for (int i=0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } void HeapAjustify(int a[],int index) { int left = Left(index); int right = Right(index); int largest=0;//记录最大值的下标 if ((left<=heapsize)&&(a[left]<a[index]))largest=index; else largest=left; if ((right<=heapsize)&&(a[right]>a[largest]))largest = right; if (largest!=index)//index为根的子树中根最大不是根 { swap(&a[largest],&a[index]);// HeapAjustify(a,largest); } } void buildMaxHeap(int a[],int arrLen) { heapsize = arrLen; for (int i=arrLen>>1;i>=0;i--) { HeapAjustify(a,i); } } void heap_sort(int a[],int aSize) { buildMaxHeap(a,aSize-1);//(1)建堆 for (int i=aSize-1;i>=1;i--) { //for(0--size){ swap(&a[0],&a[i]); //(2)堆输出 heapsize--; HeapAjustify(a,0); //(3)调整 } // } //endfor } int _tmain(int argc, _TCHAR* argv[]) { int a[]= {7,3,5,8,9,1,2,4,6}; cout<<"before :"<<endl; print(a,9); heap_sort(a,9); cout<<"after:"<<endl; print(a,9); system("pause"); return 0; }
堆是一棵完全二叉树，满足二叉树的所有性质；
对于一颗高度为h的堆，调整堆的时间为O(h);
7.归并排序
自底向上：将序列看成是n个长度为1的子序列，两两归并。
自顶向下：将序列一分为二，然后递归求解
对两堆排好序且正面朝上的扑克，每次从表面选择较小一张，直到所有牌取完。
1 // merge_sort.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include <iostream> 6 7 using namespace std; 8 9 void print(int a[],int n) 10 { 11 for (int i=0;i<n;i++) 12 { 13 cout<<a[i]<<" "; 14 } 15 cout<<endl; 16 } 17 void merge(int a[],int temp[],int llow,int rlow,int rend)//利用额外的数组来组合 18 { 19 int NumEle = rend-llow+1; 20 int lend = rlow-1; 21 int position=llow; 22 while (llow<=lend&&rlow<=rend) 23 { 24 if (a[llow]<=a[rlow])temp[position++]=a[llow++]; 25 else temp[position++]=a[rlow++]; 26 } 27 while(llow<=lend)temp[position++]=a[llow++]; 28 while(rlow<=rend)temp[position++]=a[rlow++]; 29 for (int i=0;i<NumEle;i++,rend--) 30 a[rend]=temp[rend]; 31 32 } 33 void merge_sort_1(int a[],int temp[],int low,int high)//找中点，分别递归 34 { 35 if(low>=high)return; 36 int middle = (low+high)/2; 37 merge_sort_1(a,temp,low,middle); 38 merge_sort_1(a,temp,middle+1,high); 39 merge(a,temp,low,middle+1,high); 40 } 41 42 43 void merge_sort(int a[],int size)//申请空间 44 { 45 int *temp = NULL; 46 temp = new int[size]; 47 if (temp!=NULL) 48 { 49 merge_sort_1(a,temp,0,size-1); 50 delete []temp; 51 } 52 53 } 54 55 int _tmain(int argc, _TCHAR* argv[]) 56 { 57 int a[]={7,3,2,6,8,4,5,9,1}; 58 print(a,9); 59 merge_sort(a,9); 60 print(a,9); 61 system("pause"); 62 return 0; 63 }
*分治法：对于结构是递归的算法，将原问题分解为多个规模小且类似原问题的子问题，递归求解他们，再将它们的解组合起来构成原问题的解。
采用递归式来描述递归算法的划分，求解得到简单递归的渐进界（主方法）。还有递归树法，两种常用分析法
8.计数排序
思想：对于每个输入元素x，确定比它小的数，就可以将它放到正确的位置上了。计数排序假设输入数据都属于一个小区间内的整数。
1 // CountSort.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include <iostream> 6 #include <memory> 7 8 using namespace std; 9 10 void print(int a[],int len) 11 { 12 for (int i=0;i<len;i++) 13 { 14 cout<<a[i]<<" "; 15 } 16 cout<<endl; 17 } 18 19 int findmax(int a[],int size) 20 { 21 int max=a[0]; 22 for (int i=1;i<size;i++) 23 { 24 if (a[i]>max)max=a[i]; 25 } 26 return max; 27 } 28 29 void countsort(int a[],int len,int &max) 30 { 31 int* b=(int *)malloc(len*sizeof(int)); 32 int* c=(int *)malloc((max+1)*sizeof(int)); 33 memset(b,0,len*sizeof(int)); 34 memset(c,0,(max+1)*sizeof(int)); 35 /* 36 这里for有点问题，i应该从0开始，但是结果有点误差，c[]正确. 37 从1开始结果正确，但c[]错，且说不通。 38 */ 39 for (int i=0;i<len;i++) 40 c[a[i]]=c[a[i]]+1; 41 //c[] contains the number of elements equal to i. 42 print(c,max+1); 43 44 for (int j=1;j<=max;j++) 45 c[j]=c[j]+c[j-1]; 46 //c[] now contains the number of elements less then or equal to i. 47 print(c,max+1); 48 49 for (int k=len-1;k>=0;--k) 50 { 51 /* 52 1st:k=7,a[k] is the value of array; 53 c[a[k]] is the number of elements that <= a[k]; 54 b[c[a[k]]] means a[k] was put to array b, its 55 position is c[a[k]].because there are c[a[k]]-1 56 elements before it. 57 ... 58 */ 59 b[c[a[k]]]=a[k]; 60 c[a[k]]-=1; 61 } 62 cout<<"after:"<<endl; 63 print(b,len); 64 cout<<endl; 65 free(b); 66 free(c); 67 } 68 69 int _tmain(int argc, _TCHAR* argv[]) 70 { 71 int a[]={2,5,3,0,2,3,0,3}; 72 cout<<"before:"<<endl; 73 print(a,8); 74 75 int max=findmax(a,8); 76 countsort(a,8,max); 77 system("pause"); 78 return 0; 79 }
总时间代价为theta(n+k),当k=theta(n)时，运行时间为theta(n).它不是比较排序，所以下界由于n*（lgN）。稳定排序。
9.基数排序
基数排序是通过“分配”和“收集”过程来实现排序
RADIX_SORT(A,d)
for i <- 1 to d
do use a stable sort to sort array A on digit i
// radix_sort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <math.h> using namespace std; void print(int a[],int size) { for (int i=0;i<size;i++) { cout<<a[i]<<" "; } cout<<endl; } int findmax(int a[],int &size) { int max=a[0]; for (int i=1;i<size;i++) { if (a[i]>max)max=a[i]; } return max; } // 算出数的位数 int ele_digit(int element) { int digit=0; do { element/=10; digit++; } while (element!=0); return digit; } int kth_digit(int number,int kth) { number/=pow(10.0,kth);//砍掉前 kth-1 位 return number%10; } /* 输入元素位数大小不确定，就要求最大数的位数 */ void radix_sort(int a[],int size) { int *temp[10]; /* 指针数组，每一个指针指向一个数组.因为个位数一般是从0-9，所以 这里为10 */ int count[10]={0,0,0,0,0,0,0,0,0,0};//记录每个箱子装多少个元素 int max=findmax(a,size); int maxdigit=ele_digit(max);//得到最大数的位数 for (int i=0;i<10;i++)//初始化temp,是二维数组 { temp[i]=(int *)malloc(size*sizeof(int));//每个temp变量指向一个6个元素的数组 memset(temp[i],0,size*sizeof(int)); } for (int i=0;i<maxdigit;i++)//对a[]遍历maxdigit次 { //memset(count,0,size*sizeof(int)); for (int j=0;j<size;i++)//记录元素个数 { int xx=kth_digit(a[j],i);//返回number的第k位数 temp[xx][count[xx]]=a[j];//此处有问题，我调试不出来。哪位仁兄帮帮忙 count[xx]++;//当前处理位相同的数++ } int index=0; for (int j=0;j<10;j++)//回收 { for (int k=0;k<count[j];k++) { a[index++]=temp[j][k]; } } } for (int i=0;i<10;i++) { free(temp[i]); } } int _tmain(int argc, _TCHAR* argv[]) { int a[]={22,32,19,53,47,29}; cout<<"before:"<<endl; print(a,6); radix_sort(a,6); cout<<"after:"<<endl; print(a,6); system("pause"); return 0; }
原文：http://www.cnblogs.com/lp3318/p/4711012.html
