1.冒泡排序：
思想：一共进行n-1次比较（假定序列个数为n），每次比较重都会有一个最大的元素沉底
#include<iostream> using namespace std; void BubbleSort(int a[],int length) { for(int i=0;i<length-1;i++) for(int j=0;j<length-1-i;j++) { if(a[j]>a[j+1]) { int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } }
2.选择排序：
算法思想：
在每次遍历序列时，通过将该位值元素与之后序列中的元素直接比较，获得最小的元素放到该位置
void SelectSort(int a[],int length) { int minnum; for(int i=0;i<length-1;i++) { minnum=i; for(int j=i+1;j<length;j++) if(a[j]<a[minnum]) minnum=j; if(minnum!=i) { int t=a[i]; a[i]=a[minnum]; a[minnum]=t; } } }
3.简单插入排序：
思想：通过构建有序序列，对于为排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
void StraightInsertSort(int a[],int length) { int i,j,temp; for(i=1;i<length;i++) { temp=a[i]; for(j=i-1;j>=0 && temp<a[j];j--) a[j+1]=a[j]; a[j+1]=temp;//此时j移动到前一个位置，在合适位置按行a[i] } }
4.二分查找排序：
思想：如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一种变种，称为二分查找排序。
折半插入排序所需护甲存储空间和直接插入排序相同。从时间上比较，折半插入排序仅减少了关键自检的比较次数，而记录的移动次数不变。
其实就是二分法查找与插入排序的一个组合，在已排好序的数组中用二分法查找出那个最合适的插入位置。
void BinaryInsertSort(int a[],int length) { int i,j,temp,low,high,mid; for(i=1;i<length;i++) { temp=a[i]; low=0; high=i-1; while(low<high) { mid=(low+high)/2; if(temp<a[mid]) high=mid-1; else low=mid+1; } for(j=i-1;j>=high && temp<a[j];j--) a[j+1]=a[j]; a[j+1]=temp; } }
5.希尔排序：
思想：
先取一个小于n的整数d1作为第一个增量，把序列中的全部元素分成d1组，所有距离为d1的倍数的记录被放在同一个组中，在各组内进行直接插入排序。然后，取第二个增量 d2<d1d2<d1 重复上诉的分组和排序，直至所取的增量dt=1(dt<dt−1<…⋯<d2<d1）dt=1(dt<dt−1<…⋯<d2<d1） ,即所有元素放在同一组中进行直接插入排序为止
void ShellInsert(int a[],int length,int dk) { int i,j,temp; for(i=dk;i<length;i++) { temp=a[i]; for(j=i-dk;j>=0 && temp<a[j];j-=dk) a[j+dk]=a[j]; a[j+dk]=temp; } } void shellSort(int a[],int length,int *gap,int count) { for(int i=count-1;i>=0;i--) { ShellInsert(a,length,gap[i]); } } void ShellSort(int a[],int length) { int gap[]={1,2,3,5,8,13,21,34,55,89}; shellSort(a,length,gap,9); }
6.归并排序:
思想：
归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并操作的算法原理为：
1.申请空间，使其大小为两个已经排序序列之和，用来存放合合并后的序列
2.设定两个指针，分别指向两个已经排好序的序列的起始位置。
3.比较两个指针所指向的元素，选择相对较小的元素放入合并空间中，并移动指针到下一个位置
4.重复步骤3，直到某一指针到达序列为
5将另一序列剩下的所有元素直接赋值到合并序列尾部
6.将排好序的合并空间的所有元素赋值给原序列
归并排序的具体原理（假定序列共有n个元素）：
1.将序列每相邻两个数字进行归并操作（merge）,形成floor(n/2)个序列，排序后的每个序列包含两个元素
2.将上诉序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素。
void Merge(int *array,int first,int mid,int last) { int i,j=0,begin1=first,end1=mid,begin2=mid+1,end2=last; int *temp=(int *)malloc((last-first+1)*sizeof(int)); if(temp==NULL) { cout<<"内存分配失败"<<endl; exit(1);//EXIT_FAILURE; } while(begin1<=end1 && begin2<=end2) //小于等于 { if(array[begin1]<array[begin2]) { temp[j++]=array[begin1]; begin1++; } else { temp[j++]=array[begin2]; begin2++; } } while(begin1<=end1) //第一块数组长度先于第二块数组被存入新开辟内存中 { temp[j++]=array[begin1]; begin1++; } while(begin2<=end2) { temp[j++]=array[begin2]; begin2++; } for(i=0;i<j;i++) //注意范围 array[first+i]=temp[i]; //起始地址为first+i free(temp); } void mergeSort(int *arr,int first,int last) { int mid; if(first<last) //当fist等于last时跳出迭代循环 { mid=(first+last)/2; mergeSort(arr,first,mid); mergeSort(arr,mid+1,last); Merge(arr,first,mid,last); } } void MergeSort(int *arr,int length) { mergeSort(arr,0,length-1); }
7.快速排序：
算法思想：
从序列中挑出一个元素，作为“基准”（pivot）,重新排列序列，使得所有比基准值小的元素都交换到基准的前面，所有比基准大的元素都放在基准后面，这成为分割（partion）操作,然后递归将基准前面的序列和基准后面的序列进行分割操作，直到序列的大小为零或一，这是该序列已经排序好了。在每次迭代中，至少有一个元素放置到了它最后应该在的位置。
int Partition(int *a,int first,int last) //双向排序 { int t=first+rand()%(last-first); int pivot=a[t]; int temp=a[t]; a[t]=a[last]; a[last]=temp; int i=first-1,j=last; while(1) { while(a[++i]<pivot); while(a[--j]>pivot); if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } else break; } temp=a[i]; a[i]=a[last]; a[last]=temp; return i; } void QSort(int *arr,int first,int last) { int pivot_loc; if(first<last) { pivot_loc=Partition(arr,first,last); QSort(arr,first,pivot_loc-1); QSort(arr,pivot_loc+1,last); } } void QuickSort(int *arr,int length) { QSort(arr,0,length-1); }
8.堆排序：
算法思想：
先将完全二叉树以数组的方式存储，按照根节点—左子树—右子树的顺序，首先建立大顶堆，然后将数组中最后一个元素与堆中第一个元素交换，此时最大元素已排好序。将除最后一个元素之外的剩下的元素重新建堆，循环往复下去直到堆为空。
typedef int ElemType; void HeapAdjust(ElemType H[], int start,int end) { ElemType temp= H[start]; for(int i=2*start+1;i<=end;i*=2) { //根节点从0开始，所以i节点的左右孩子节点的下标为2*i+1和2*i+2 if(i<end && H[i]<H[i+1]) { ++i; //i为较大的记录下标 } if(temp>H[i]) break; H[start]= H[i]; start=i; } H[start]= temp; //插入最开始的根节点元素 } void HeapSort(ElemType A[],int n) { //先建立大顶堆 for(int i=n/2;i>=0 ;--i) //从最后一个元素父节点开始建堆 HeapAdjust(A,i,n); //进行排序 for(int i=n-1;i>0;--i) { ElemType temp=A[i]; A[i]=A[0]; A[0]=temp; //将剩下的无序元素继续调整为大顶堆 HeapAdjust(A,0,i-1); } }
测试主程序如下：
#include<iostream> using namespace std; int main() { int a[10]={9,10,3,5,12,10,1,8,100,4}; //SelectSort(a,10); //BubbleSort(a,10); //StraightInsertSort(a,10); //BinaryInsertSort(a,10); //ShellSort(a,10); //MergeSort(a,10); //QuickSort(a,10); HeapSort(a,10); for(int i=0;i<10;i++) cout<<a[i]<<" "; cout<<endl; }
欢迎加入qq群：877061392
