呵呵，发现了超全的排序代码！！和大家分享！(页 1) - C++论坛 - C++ Builder

风致发表于 2007-9-23 20:05

呵呵，发现了超全的排序代码！！和大家分享！

关于排序的认识 排序总的可以分为插入排序，交换排序，选择排序，归并排序，基数排序等。
其中插入排序又可以细分为直接插入排序，折半排序，希尔排序。 直接排序的基本思想是：当插入第i （i>=1）个对象时，前面的v[0]，v[1]，…….v[i-1]已经排好序，这时，用v[i]的关键码与v[i-1],v[i-2]……的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。直接插入排序的时间复杂度为n2,直接插入排序是一种稳定的排序方法。 折半排序的基本思想是：设在顺序表中有一个对象序列v[0]，v[1]，….v[n-1]，其中，v[0]，v[1]，….v[i-1]是已经排好序的对象。在插入v[i]时，利用折半查找法寻找v[i]的插入位置。折半插入是一种稳定的排序方法。 希尔排序：当待排序的数列很长时，（即n很大时），关键码平均比较次数和对象平均移动次数大约在n1.25（即n的1.25次方，以下同样）到1.6n1.25范围内。
交换排序又可细分为冒泡排序，快速排序。 冒泡排序的基本思想是：设待排序的数列的大小为n，首先比较v[n-2]和v[n-1]的大小，如果v[n-2]>v[n-1],则交换v[n-2]和v[n-1]，然后对v[n-2]和v[n-3]作相同的处理，如此处理，直到处理完v[0]和v[1],这个称为一趟冒泡，所以只要经过n-1 趟冒泡就可以排好所有对象。在最坏情况下总的关键码比较次数为0.5n(n-1),对象移动次数为1.5n（n-1） 快速排序的基本思想是：取待排序的数列的某个对象（例如第一个对象）作为基准，将对象分为左右两个数列，左边的全都小于基准，右边的全都大于基准，然后对左右两个树列重复以上操作，直到全部完成。它是一种不稳定的方法，对于待排序的数列很大时，快速排序的确很快，但当待排序的数列很小时，它往往比其它简单的排序方法还要慢。
选择排序又可以细分为直接选择排序，堆排序。 直接选择排序的最坏情况是每一趟都要进行交换，总的对象移动次数是3(n-1)。 堆排序可以分为两个步骤：首先，根据初始输入数据，利用堆的调整算法FilterDown()形成初始堆，第二步通过一系列的对象交换和重新调整堆进行排序。堆排序的是一个不稳定的排序方法，并且当待排序的数列很大时，堆排序不可取。
归并排序就是将两个或两个以上的有序表合并成一个新的有序表。
基数排序的基本思想是：待排序的对象按m个关键码key[0],…..key[m-1]排序，每个对象的关键码域用一个数组key[m]表示，对各关键码的排序采用箱排序。
从上面可以得出结论（本人观点），当待排序的数列很小时，可以采取直接插入排序，折半排序，希尔排序，直接选择排序，堆排序，归并排序，基数排序等众多排序方法，但当待排序的数列很大时，采用快速排序为优。
就平均性能而言，我认为快速排序最好。 冒泡排序： void CSortDlg::bubble_sort(int x[]){ //对数组x[]逐趟进行比较，遇到逆序即交换 int i =1;int exchange=1;//当exchange为0时，则停止排序 while((i<10 )&&exchange){// BubbleExchange( x, i, exchange); i++; } } void CSortDlg::BubbleExchange(int x[],int i,int exchange){ exchange = 0;//假定元素未交换 for(int j =9;j>=i;j--){ if(x[j-1]>x[j])//发生了逆序 { int temp = x[j-1];//交换 x[j-1]=x[j]; x[j] = temp; exchange = 1;//做“发生了交换”的标志 } } } 直接插入排序： void CSortDlg::InsertionSort(int x[]) { for(int i=1;i<10;i++) { Insert(x,i); } } void CSortDlg::Insert(int x[],int i) { int temp=x[i]; int j=i; while (j>0&&temp<x[j-1]) { x[j]=x[j-1]; j--; } x[j]=temp; } 希尔排序： void CSortDlg::Shellsort(int x[]) { int gap=10/2;//增量的初始值 while (gap)//循环条件是gap>=1 { ShellInsert(x,gap);//按增量gap划分子序列，分别进行插入排序 gap=gap==2?1:(int)(gap/2);//缩小增量gap } } void CSortDlg::ShellInsert(int x[],const int gap) { for(int i=gap;i<10;i++)//各子序列轮流执行插入排序 { int temp=x[i];int j=i;//暂存待插入对象 while (j>=gap&&temp<x[j-gap]) {//当前插入元素比位于j-gap的元素小，则位于j-gap的元 //素后移 x[j]=x[j-gap]; j-=gap;//后移到第j个位置，j指标前指 } x[j]=temp;//插入 } } 归并排序： void CSortDlg::MergeSort(int x[]) { int temp_array[10]; int len=1; while (len<10) { //归并排序 MergePass(x,temp_array,len);//一趟两路归并后归并项长度加倍 len*=2; MergePass(temp_array,x,len); len*=2; } // delete[] temp_array; } void CSortDlg::MergePass(int init_array[],int merge_array[],const int len) {//一趟归并排序 int i=0; while (i+2*len<=9) {//对长度为len的子表两两归并，直到表中剩余元素个数不足2*len为止 merge(init_array,merge_array,i,i+len-1,i+2*len-1); i+=2*len; } if (i+len<=9) merge(init_array,merge_array,i,i+len-1,9); else for (int j=i;j<=9;j++) {//若不能做归并，就复制 merge_array[j]=init_array[j]; } } void CSortDlg::merge(int init_array[],int merge_array[],const int l,const int m,const int n) { int i=l,j=m+1,k=l; while (i<=m&&j<=n) if (init_array[i]<=init_array[j]) { merge_array[k]=init_array[i]; i++;k++; } else { merge_array[k]=init_array[j]; j++;k++; } if (i<=m) for (int n1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) { merge_array[n1]=init_array[n2]; } else for (int n1=k, n2=j;n1<=n&&n2<=n;n1++,n2++) { merge_array[n1]= init_array[n2]; } } 折半插入排序： void CSortDlg::BinaryInsertSort(int x[]) { for (int i=1;i<10;i++) { BinaryInsert(x,i); } } void CSortDlg::BinaryInsert(int x[],int i) { int left=0,right=i-1; int temp=x[i]; while (left<=right) //利用折半查找找插入位置 { int middle=(left+right)/2;//取中点 if (temp<x[middle]) //插入值小于中点值 { right=middle-1;//向左缩小区间 } else //否则向右缩小区间 left=middle+1; } for (int k=i-1;k>=left;k--)//成块移动，空出插入位置 { x[k+1]=x[k]; } x[align=left]=temp;//插入 } 直接选择排序： void CSortDlg::SelectSort(int x[]) { for (int i=0;i<9;i++) { SelectExchange(x,i); } } void CSortDlg::SelectExchange(int x[],const int i) { int k=i; for (int j=i+1;j<10;j++) if(x[j]<x[k]) k=j; if(k!=i) { int temp=x[i]; x[i]=x[k]; x[k]=temp; } } 基数排序： int CSortDlg::digit(int data,int n) { int i = -1; for (int k = 0; k <= n;++k) { i = data % RADIX; data = data / RADIX; } return i; } void CSortDlg::SortOnDigit(int* data,int d,int left,int right) { int c[RADIX] = {0}; //c[i]记录d位上为i的元素个数 for (int i = left; i <= right ;i++ ) { ++c[digit(data[i],d)]; //记录d位上相同的数据个数 } for (int j = 1;j < RADIX ;++j ) { c[j] += c[j-1]; //很明显，d位上较大（就是j的值），元素越大 //c[j]记录d位上小于等于j的元素的个数 } int len = right - left +1; int* tmp = new int[len]; //知道了有多少元素在d位置上比自己小，则可以确定d位上的值的元素位置 for (int k = right; k >= left; k--) { tmp[--c[digit(data[k],d)]] = data[k]; } for (int m = left;m <= right ;++m ) { data[m] = tmp[m - left]; } delete[] tmp; } void CSortDlg::RadixSort(int* data,int left,int right) { for (int i = 0;i < WIDTH; ++i) { SortOnDigit(data,i,left,right); } } 快速排序： void CSortDlg::quick_sort(int x[], int low, int high) //快速排序函数的实现过程 { 
 int pivotkey; if(low<high) { pivotkey=partition(x,low,high); quick_sort(x,low,pivotkey-1); quick_sort(x,pivotkey+1,high); } } int CSortDlg::partition(int x[],int low,int high) { int pivotkey; pivotkey=x[low]; while(low<high) { while(low<high&&x[high]>pivotkey) --high; x[low]=x[high]; while(low<high&&x[low]<pivotkey) ++low; x[high]=x[low]; } // x[low]=x[0]; x[low]=pivotkey; return low; } 堆排序： void CSortDlg::HeapSort(int*list,int num) { for(int i=(num-2)/2;i>=0;i--) FiltDown(list,i,num-1); for(i=num-1;i>=1;i--) { int temps=list[0]; list[0]=list[i]; list[i]=temps; FiltDown(list,0,i-1); // if(m_mark==1) // show(list); } } void CSortDlg::FiltDown(int*list,int i,int end) { int c=i;int ch=2*i+1; int temp=list[i]; while(ch<=end) { if(ch<end&&list[ch]<list[ch+1]) ch++; if(temp>=list[ch])break; else { list[c]=list[ch]; c=ch;ch=2*ch+1; } } list[c]=temp; }

鹏云翅 发表于 2007-9-24 02:02

收藏一下
[align=right][color=#000066][此贴子已经被作者于2007-9-24 2:03:33编辑过][/color][/align]

页: [1]