- 浏览: 21923 次
- 性别:
- 来自: 南京
最新评论
排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法,那么哪些排序算法比较有效率,哪些算法在特定场合比较有效,下面将用C++实现各种算法,并且比较他们的效率,让我们对各种排序有个更深入的了解。
minheap.h 用于堆排序:
view sourceprint?001 //使用时注意将关键码加入
002 #ifndef MINHEAP_H
003 #define MINHEAP_H
004 #include <assert.h>
005 #include <iostream>
006 using std::cout;
007 using std::cin;
008 using std::endl;
009 using std::cerr;
010 #include <stdlib.h>
011 //const int maxPQSize = 50;
012 template <class Type> class MinHeap {
013 public:
014 MinHeap ( int maxSize );//根据最大长度建堆
015 MinHeap ( Type arr[], int n );//根据数组arr[]建堆
016 ~MinHeap ( ) { delete [] heap; }
017 const MinHeap<Type> & operator = ( const MinHeap &R );//重载赋值运算符
018 int Insert ( const Type &x );//插入元素
019 int RemoveMin ( Type &x );//移除关键码最小的元素,并赋给x
020 int IsEmpty ( ) const { return CurrentSize == 0; }//检查堆是否为空
021 int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//检查对是否满
022 void MakeEmpty ( ) { CurrentSize = 0; }//使堆空
023 private:
024 enum { DefaultSize = 50 };//默认堆的大小
025 Type *heap;
026 int CurrentSize;
027 int MaxHeapSize;
028 void FilterDown ( int i, int m );//自上向下调整堆
029 void FilterUp ( int i );//自下向上调整堆
030 };
031
032 template <class Type> MinHeap <Type>::MinHeap ( int maxSize )
033 {
034 //根据给定大小maxSize,建立堆对象
035 MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize; //确定堆大小
036 heap = new Type [MaxHeapSize]; //创建堆空间
037 CurrentSize = 0; //初始化
038 }
039
040 template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n )
041 {
042 //根据给定数组中的数据和大小,建立堆对象
043 MaxHeapSize = DefaultSize < n ? n : DefaultSize;
044 heap = new Type [MaxHeapSize];
045 if(heap==NULL){cerr <<"fail" <<endl;exit(1);}
046 for(int i =0; i< n; i++)
047 heap[i] = arr[i]; //数组传送
048 CurrentSize = n; //当前堆大小
049 int currentPos = (CurrentSize-2)/2; //最后非叶
050 while ( currentPos >= 0 ) {
051 //从下到上逐步扩大,形成堆
052 FilterDown ( currentPos, CurrentSize-1 );
053 currentPos-- ;
054 //从currentPos开始,到0为止, 调整currentPos--; }
055 }
056 }
057
058 template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap )
059 {
060 // 结点i的左、右子树均为堆,调整结点i
061 int i = start, j = 2*i+1; // j 是 i 的左子女
062 Type temp = heap[i];
063 while ( j <= EndOfHeap ) {
064 if ( j < EndOfHeap && heap[j] > heap[j+1] )
065 j++;//两子女中选小者
066 if ( temp<= heap[j] ) break;
067 else { heap[i] = heap[j]; i = j; j = 2*j+1; }
068 }
069 heap[i] = temp;
070 }
071
072 template <class Type> int MinHeap<Type>::Insert ( const Type &x )
073 {
074 //在堆中插入新元素 x
075 if ( CurrentSize == MaxHeapSize ) //堆满
076 {
077 cout << "堆已满" << endl; return 0;
078 }
079 heap[CurrentSize] = x; //插在表尾
080 FilterUp (CurrentSize); //向上调整为堆
081 CurrentSize++; //堆元素增一
082 return 1;
083 }
084
085 template <class Type> void MinHeap<Type>::FilterUp ( int start )
086 {
087 //从 start 开始,向上直到0,调整堆
088 int j = start, i = (j-1)/2; // i 是 j 的双亲
089 Type temp = heap[j];
090 while ( j > 0 ) {
091 if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break;
092 else { heap[j] = heap[i]; j = i; i = (i -1)/2; }
093 }
094 heap[j] = temp;
095 }
096 template <class Type> int MinHeap <Type>::RemoveMin ( Type &x )
097 {
098 if ( !CurrentSize )
099 {
100 cout << "堆已空 " << endl;
101 return 0;
102 }
103 x = heap[0]; //最小元素出队列
104 heap[0] = heap[CurrentSize-1];
105 CurrentSize--; //用最小元素填补
106 FilterDown ( 0, CurrentSize-1 );
107 //从0号位置开始自顶向下调整为堆
108 return 1;
109 }
110 #endif
sort.cpp 主要的排序函数集包括冒泡排序、快速排序、插入排序、希尔排序、计数排序:
view sourceprint?001 //n^2
002 //冒泡排序V[n]不参与排序
003 void BubbleSort (int V[], int n )
004 {
005 bool exchange; //设置交换标志置
006 for ( int i = 0; i < n; i++ ){
007 exchange=false;
008 for (int j=n-1; j>i; j--) { //反向检测,检查是否逆序
009 if (V[j-1] > V[j]) //发生逆序,交换相邻元素
010 {
011 int temp=V[j-1];
012 V[j-1]=V[j];
013 V[j]=temp;
014 exchange=true;//交换标志置位
015 }
016 }
017
018 if (exchange == false)
019 return; //本趟无逆序,停止处理
020 }
021 }
022
023
024
025 //插入排序,L[begin],L[end]都参与排序
026 void InsertionSort ( int L[], const int begin, const int end)
027 {
028 //按关键码 Key 非递减顺序对表进行排序
029 int temp;
030 int i, j;
031 for ( i = begin; i < end; i++ )
032 {
033 if (L[i]>L[i+1])
034 {
035 temp = L[i+1];
036 j=i;
037 do
038 {
039 L[j+1]=L[j];
040 if(j == 0)
041 {
042 j--;
043 break;
044 }
045 j--;
046
047 } while(temp<L[j]);
048 L[j+1]=temp;
049 }
050 }
051 }
052 //n*logn
053 //快速排序A[startingsub],A[endingsub]都参与排序
054 void QuickSort( int A[], int startingsub, int endingsub)
055 {
056 if ( startingsub >= endingsub )
057 ;
058 else{
059 int partition;
060 int q = startingsub;
061 int p = endingsub;
062 int hold;
063
064 do{
065 for(partition = q ; p > q ; p--){
066 if( A[q] > A[p]){
067 hold = A[q];
068 A[q] = A[p];
069 A[p] = hold;
070 break;
071 }
072 }
073 for(partition = p; p > q; q++){
074 if(A[p] < A[q]){
075 hold = A[q];
076 A[q] = A[p];
077 A[p] = hold;
078 break;
079 }
080 }
081
082 }while( q < p );
083 QuickSort( A, startingsub, partition - 1 );
084 QuickSort( A, partition + 1, endingsub );
085 }
086 }
087
088 //希尔排序,L[left],L[right]都参与排序
089 void Shellsort( int L[], const int left, const int right)
090 {
091 int i, j, gap=right-left+1; //增量的初始值
092 int temp;
093 do{
094 gap=gap/3+1; //求下一增量值
095 for(i=left+gap; i<=right; i++)
096 //各子序列交替处理
097 if( L[i]<L[i-gap]){ //逆序
098 temp=L[i]; j=i-gap;
099 do{
100 L[j+gap]=L[j]; //后移元素
101 j=j-gap; //再比较前一元素
102 }while(j>left&&temp<L[j]);
103 L[j+gap]=temp; //将vector[i]回送
104 }
105 }while(gap>1);
106 }
107
108 //n
109 //计数排序,L[n]不参与排序
110 void CountingSort( int L[], const int n )
111 {
112 int i,j;
113 const int k =1001;
114 int tmp[k];
115 int *R;
116 R = new int[n];
117 for(i=0;i<k;i++) tmp[i]= 0;
118 for(j=0;j<n;j++) tmp[L[j]]++;
119 //执行完上面的循环后,tmp[i]的值是L中等于i的元素的个数
120 for(i=1;i<k;i++)
121 tmp[i]=tmp[i]+tmp[i-1]; //执行完上面的循环后,
122 //tmp[i]的值是L中小于等于i的元素的个数
123 for(j=n-1;j>=0;j--) //这里是逆向遍历,保证了排序的稳定性
124 {
125
126 R[tmp[L[j]]-1] = L[j];
127 //L[j]存放在输出数组R的第tmp[L[j]]个位置上
128 tmp[L[j]]--;
129 //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数
130
131 }
132 for(j=0;j<n;j++) L[j] = R[j];
133 }
134
135 //基数排序
136 void printArray( const int Array[], const int arraySize );
137 int getDigit(int num, int dig);
138 const int radix=10; //基数
139 void RadixSort(int L[], int left, int right, int d){
140 //MSD排序算法的实现。从高位到低位对序列划分,实现排序。d是第几位数,d=1是最低位。left和right是待排序元素子序列的始端与尾端。
141 int i, j, count[radix], p1, p2;
142 int *auxArray;
143 int M = 5;
144 auxArray = new int[right-left+1];
145 if (d<=0) return; //位数处理完递归结束
146 if (right-left+1<M){//对于小序列可调用直接插入排序
147 InsertionSort(L,left,right); return;
148 }
149 for (j=0; j<radix; j++) count[j]=0;
150 for (i=left; i<=right; i++) //统计各桶元素的存放位置
151 count[getDigit(L[i],d)]++;
152 for (j=1; j<radix; j++) //安排各桶元素的存放位置
153 count[j]=count[j]+count[j-1];
154 for (i=right; i>=left; i--){ //将待排序序列中的元素按位置分配到各个桶中,存于助数组auxArray中
155 j=getDigit(L[i],d); //取元素L[i]第d位的值
156 auxArray[count[j]-1]=L[i]; //按预先计算位置存放
157 count[j]--; //计数器减1
158 }
159 for (i=left, j=0; i<=right; i++, j++)
160 L[i]=auxArray[j]; //从辅助数组顺序写入原数组
161 delete []auxArray;
162 for (j=0; j<radix; j++){ //按桶递归对d-1位处理
163 p1=count[j]+left; //取桶始端,相对位置,需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
164 (j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端
165 // delete []count;
166 if(p1<p2){
167 RadixSort(L, p1, p2, d-1); //对桶内元素进行基数排序
168 // printArray(L,10);
169 }
170 }
171
172 }
173
174 int getDigit(int num, int dig)
175 {
176 int myradix = 1;
177 /* for(int i = 1;i<dig;i++)
178 {
179 myradix *= radix;
180 }*/
181 switch(dig)
182 {
183 case 1:
184 myradix = 1;
185 break;
186 case 2:
187 myradix = 10;
188 break;
189 case 3:
190 myradix = 1000;
191 break;
192 case 4:
193 myradix = 10000;
194 break;
195 default:
196 myradix = 1;
197 break;
198 }
199 return (num/myradix)%radix;
200 }
maintest.cpp 测试例子:
view sourceprint?001 #include<iostream>
002 using std::cout;
003 using std::cin;
004 using std::endl;
005 #include <cstdlib>
006 #include <ctime>
007 #include<iostream>
008 using std::cout;
009 using std::cin;
010 using std::ios;
011 using std::cerr;
012 using std::endl;
013 #include<iomanip>
014 using std::setw;
015 using std::fixed;
016 #include<fstream>
017 using std::ifstream;
018 using std::ofstream;
019 using std::flush;
020 #include<string>
021 using std::string;
022 #include <stdio.h>
023 #include <stdlib.h>
024 #include <time.h>
025 #include"minheap.h"
026 void BubbleSort(int arr[], int size);//冒泡排序
027 void QuickSort( int A[], int startingsub, int endingsub);//快速排序
028 void InsertionSort ( int L[], const int begin,const int n);//插入排序
029 void Shellsort( int L[], const int left, const int right);//希尔排序
030 void CountingSort( int L[], const int n );//计数排序
031 int getDigit(int num, int dig);//基数排序中获取第dig位的数字
032 void RadixSort(int L[], int left, int right, int d);//基数排序
033 void printArray( const int Array[], const int arraySize );//输出数组
034
035 int main()
036 {
037 clock_t start, finish;
038 double duration;
039 /* 测量一个事件持续的时间*/
040 ofstream *ofs;
041 string fileName = "sortResult.txt";
042 ofs = new ofstream(fileName.c_str(),ios::out|ios::app);
043 const int size = 100000;
044 int a[size];
045 int b[size];
046 srand(time(0));
047 ofs->close();
048 for(int i = 0; i < 20;i++)
049 {
050 ofs->open(fileName.c_str(),ios::out|ios::app);
051 if( ofs->fail()){
052 cout<<"!!";
053 ofs->close();
054 }
055
056 for(int k =0; k <size;k++)
057 {
058 a[k] = rand()%1000;
059 b[k] = a[k];
060
061 }
062 /* for( k =0; k <size;k++)
063 {
064 a[k] = k;
065 b[k] = a[k];
066
067 } */
068 //printArray(a,size);
069 //计数排序
070 for( k =0; k <size;k++)
071 {
072 a[k] = b[k];
073 }
074 start = clock();
075 CountingSort(a,size);
076
077 finish = clock();
078 // printArray(a,size);
079
080 duration = (double)(finish - start) / CLOCKS_PER_SEC;
081 printf( "%s%f seconds\n", "计数排序:",duration );
082 *ofs<<"第"<<i<<"次:\n " <<"排序内容:0~999共" << size << " 个整数\n" ;
083 *ofs<<"第"<<i<<"次计数排序:\n " <<" Time: " <<fixed<< duration << " seconds\n";
084 //基数排序
085 for( k =0; k <size;k++)
086 {
087 a[k] = b[k];
088 }
089 start = clock();
090 RadixSort(a, 0,size-1, 3);
091 finish = clock();
092 // printArray(a,size);
093
094 duration = (double)(finish - start) / CLOCKS_PER_SEC;
095 printf( "%s%f seconds\n", "基数排序:",duration );
096 *ofs<<"第"<<i<<"次基数排序:\n " <<" Time: " << duration << " seconds\n";
097 //堆排序
098 MinHeap<int> mhp(a,size);
099 start = clock();
100 for( k =0; k <size;k++)
101 {
102 mhp.RemoveMin(a[k]);
103 }
104 finish = clock();
105 // printArray(a,size);
106 duration = (double)(finish - start) / CLOCKS_PER_SEC;
107 printf( "%s%f seconds\n", "堆排序:",duration );
108 *ofs<<"第"<<i<<"次堆排序:\n " <<" Time: " << duration << " seconds\n";
109 //快速排序
110 for( k =0; k <size;k++)
111 {
112 a[k] = b[k];
113
114 }
115 //printArray(a,size);
116 start = clock();
117 QuickSort(a,0,size-1);
118 finish = clock();
119 // printArray(a,size);
120 duration = (double)(finish - start) / CLOCKS_PER_SEC;
121 printf( "%s%f seconds\n", "快速排序:",duration );
122 *ofs<<"第"<<i<<"次快速排序:\n " <<" Time: " << duration << " seconds\n";
123
124 //希尔排序
125 for( k =0; k <size;k++)
126 {
127 a[k] = b[k];
128 }
129 start = clock();
130 Shellsort(a,0,size-1);
131
132 finish = clock();
133 // printArray(a,size);
134
135 duration = (double)(finish - start) / CLOCKS_PER_SEC;
136 printf( "%s%f seconds\n", "希尔排序:",duration );
137 *ofs<<"第"<<i<<"次希尔排序:\n " <<" Time: " << duration << " seconds\n";
138
139 //插入排序
140 for( k =0; k <size;k++)
141 {
142 a[k] = b[k];
143 }
144 start = clock();
145 InsertionSort (a,0,size-1);
146 finish = clock();
147 // printArray(a,size);
148
149 duration = (double)(finish - start) / CLOCKS_PER_SEC;
150 printf( "%s%f seconds\n", "插入排序:",duration );
151 *ofs<<"第"<<i<<"次插入排序:\n " <<" Time: " << duration << " seconds\n";
152 //冒泡排序
153 for( k =0; k <size;k++)
154 {
155 a[k] = b[k];
156 }
157 start = clock();
158 BubbleSort(a,size);
159 finish = clock();
160 // printArray(a,size);
161
162 duration = (double)(finish - start) / CLOCKS_PER_SEC;
163 printf( "%s%f seconds\n", "冒泡排序:",duration );
164 *ofs<<"第"<<i<<"次冒泡排序:\n " <<" Time: " << duration << " seconds\n";
165
166 ofs->close();
167 }
168 return 0;
169 }
170
171 void printArray( const int Array[], const int arraySize )
172 {
173 for( int i = 0; i < arraySize; i++ ) {
174 cout << Array[ i ] << " ";
175 if ( i % 20 == 19 )
176 cout << endl;
177 }
178 cout << endl;
179 }
排序算法性能仿真:
排序内容:从0~999中随机产生,共100000 个整数,该表中单位为秒。
次数 计数排序 基数排序 堆排序 快速排序 希尔排序 直接插入排序 冒泡排序
1 0.0000 0.0310 0.0470 0.0470 0.0310 14.7970 58.0930
2 0.0000 0.0470 0.0310 0.0470 0.0470 16.2500 53.3280
3 0.0000 0.0310 0.0310 0.0310 0.0310 14.4850 62.4380
4 0.0000 0.0320 0.0320 0.0470 0.0310 17.1090 61.8440
5 0.0000 0.0310 0.0470 0.0470 0.0310 16.9380 62.3280
6 0.0000 0.0310 0.0310 0.0470 0.0310 16.9380 57.7030
7 0.0000 0.0310 0.0470 0.0310 0.0310 16.8750 61.9380
8 0.0150 0.0470 0.0310 0.0470 0.0320 17.3910 62.8600
9 0.0000 0.0320 0.0470 0.0460 0.0310 16.9530 62.2660
10 0.0000 0.0470 0.0310 0.0470 0.0310 17.0160 60.1410
11 0.0000 0.0930 0.0780 0.0320 0.0310 14.6090 54.6570
12 0.0000 0.0310 0.0320 0.0310 0.0310 15.0940 62.3430
13 0.0000 0.0310 0.0310 0.0470 0.0310 17.2340 61.9530
14 0.0000 0.0320 0.0470 0.0470 0.0310 16.9060 61.0620
15 0.0000 0.0320 0.0320 0.0460 0.0320 16.7810 62.5310
16 0.0000 0.0470 0.0470 0.0620 0.0310 17.2350 57.1720
17 0.0150 0.0160 0.0320 0.0470 0.0310 14.1400 52.0320
18 0.0150 0.0160 0.0310 0.0310 0.0310 14.1100 52.3590
19 0.0000 0.0310 0.0320 0.0460 0.0320 14.1090 51.8750
20 0.0000 0.0310 0.0320 0.0460 0.0320 14.0780 52.4840
21 0.0150 0.0780 0.0470 0.0470 0.0310 16.3750 59.5150
22 0.0000 0.0310 0.0310 0.0470 0.0320 16.8900 60.3440
23 0.0000 0.0310 0.0310 0.0310 0.0310 16.3440 60.0930
24 0.0000 0.0310 0.0310 0.0470 0.0310 16.3440 60.5780
25 0.0000 0.0320 0.0470 0.0470 0.0470 16.3590 59.7810
26 0.0160 0.0470 0.0310 0.0470 0.0310 16.1250 61.0620
27 0.0000 0.0310 0.0470 0.0470 0.0310 16.7810 59.6100
28 0.0150 0.0320 0.0320 0.0470 0.0310 16.9220 56.8130
29 0.0000 0.0310 0.0310 0.0310 0.0310 15.0790 57.8120
30 0.0000 0.0310 0.0320 0.0460 0.0320 14.7810 58.8280
31 0.0000 0.0310 0.0310 0.0470 0.0310 15.8590 59.1400
32 0.0000 0.0470 0.0320 0.0310 0.0310 16.0940 59.1560
33 0.0000 0.0470 0.0310 0.0310 0.0310 15.9850 59.1400
34 0.0000 0.0310 0.0310 0.0470 0.0320 16.0150 59.2500
35 0.0000 0.0310 0.0470 0.0470 0.0310 16.7660 57.9840
36 0.0000 0.0310 0.0320 0.0470 0.0310 15.3750 59.0470
37 0.0000 0.0320 0.0460 0.0470 0.0320 16.0310 58.9060
38 0.0000 0.0310 0.0310 0.0470 0.0310 15.9530 57.2650
39 0.0160 0.0310 0.0470 0.0470 0.0310 15.9530 57.5160
40 0.0150 0.0310 0.0320 0.0470 0.0310 14.7030 56.6710
平均值 0.0031 0.0360 0.0372 0.0437 0.0320 15.9946 58.7480
最小值 0.0000 0.0160 0.0310 0.0310 0.0310 14.0780 51.8750
最大值 0.0160 0.0930 0.0780 0.0620 0.0470 17.3910 62.8600
minheap.h 用于堆排序:
view sourceprint?001 //使用时注意将关键码加入
002 #ifndef MINHEAP_H
003 #define MINHEAP_H
004 #include <assert.h>
005 #include <iostream>
006 using std::cout;
007 using std::cin;
008 using std::endl;
009 using std::cerr;
010 #include <stdlib.h>
011 //const int maxPQSize = 50;
012 template <class Type> class MinHeap {
013 public:
014 MinHeap ( int maxSize );//根据最大长度建堆
015 MinHeap ( Type arr[], int n );//根据数组arr[]建堆
016 ~MinHeap ( ) { delete [] heap; }
017 const MinHeap<Type> & operator = ( const MinHeap &R );//重载赋值运算符
018 int Insert ( const Type &x );//插入元素
019 int RemoveMin ( Type &x );//移除关键码最小的元素,并赋给x
020 int IsEmpty ( ) const { return CurrentSize == 0; }//检查堆是否为空
021 int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//检查对是否满
022 void MakeEmpty ( ) { CurrentSize = 0; }//使堆空
023 private:
024 enum { DefaultSize = 50 };//默认堆的大小
025 Type *heap;
026 int CurrentSize;
027 int MaxHeapSize;
028 void FilterDown ( int i, int m );//自上向下调整堆
029 void FilterUp ( int i );//自下向上调整堆
030 };
031
032 template <class Type> MinHeap <Type>::MinHeap ( int maxSize )
033 {
034 //根据给定大小maxSize,建立堆对象
035 MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize; //确定堆大小
036 heap = new Type [MaxHeapSize]; //创建堆空间
037 CurrentSize = 0; //初始化
038 }
039
040 template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n )
041 {
042 //根据给定数组中的数据和大小,建立堆对象
043 MaxHeapSize = DefaultSize < n ? n : DefaultSize;
044 heap = new Type [MaxHeapSize];
045 if(heap==NULL){cerr <<"fail" <<endl;exit(1);}
046 for(int i =0; i< n; i++)
047 heap[i] = arr[i]; //数组传送
048 CurrentSize = n; //当前堆大小
049 int currentPos = (CurrentSize-2)/2; //最后非叶
050 while ( currentPos >= 0 ) {
051 //从下到上逐步扩大,形成堆
052 FilterDown ( currentPos, CurrentSize-1 );
053 currentPos-- ;
054 //从currentPos开始,到0为止, 调整currentPos--; }
055 }
056 }
057
058 template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap )
059 {
060 // 结点i的左、右子树均为堆,调整结点i
061 int i = start, j = 2*i+1; // j 是 i 的左子女
062 Type temp = heap[i];
063 while ( j <= EndOfHeap ) {
064 if ( j < EndOfHeap && heap[j] > heap[j+1] )
065 j++;//两子女中选小者
066 if ( temp<= heap[j] ) break;
067 else { heap[i] = heap[j]; i = j; j = 2*j+1; }
068 }
069 heap[i] = temp;
070 }
071
072 template <class Type> int MinHeap<Type>::Insert ( const Type &x )
073 {
074 //在堆中插入新元素 x
075 if ( CurrentSize == MaxHeapSize ) //堆满
076 {
077 cout << "堆已满" << endl; return 0;
078 }
079 heap[CurrentSize] = x; //插在表尾
080 FilterUp (CurrentSize); //向上调整为堆
081 CurrentSize++; //堆元素增一
082 return 1;
083 }
084
085 template <class Type> void MinHeap<Type>::FilterUp ( int start )
086 {
087 //从 start 开始,向上直到0,调整堆
088 int j = start, i = (j-1)/2; // i 是 j 的双亲
089 Type temp = heap[j];
090 while ( j > 0 ) {
091 if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break;
092 else { heap[j] = heap[i]; j = i; i = (i -1)/2; }
093 }
094 heap[j] = temp;
095 }
096 template <class Type> int MinHeap <Type>::RemoveMin ( Type &x )
097 {
098 if ( !CurrentSize )
099 {
100 cout << "堆已空 " << endl;
101 return 0;
102 }
103 x = heap[0]; //最小元素出队列
104 heap[0] = heap[CurrentSize-1];
105 CurrentSize--; //用最小元素填补
106 FilterDown ( 0, CurrentSize-1 );
107 //从0号位置开始自顶向下调整为堆
108 return 1;
109 }
110 #endif
sort.cpp 主要的排序函数集包括冒泡排序、快速排序、插入排序、希尔排序、计数排序:
view sourceprint?001 //n^2
002 //冒泡排序V[n]不参与排序
003 void BubbleSort (int V[], int n )
004 {
005 bool exchange; //设置交换标志置
006 for ( int i = 0; i < n; i++ ){
007 exchange=false;
008 for (int j=n-1; j>i; j--) { //反向检测,检查是否逆序
009 if (V[j-1] > V[j]) //发生逆序,交换相邻元素
010 {
011 int temp=V[j-1];
012 V[j-1]=V[j];
013 V[j]=temp;
014 exchange=true;//交换标志置位
015 }
016 }
017
018 if (exchange == false)
019 return; //本趟无逆序,停止处理
020 }
021 }
022
023
024
025 //插入排序,L[begin],L[end]都参与排序
026 void InsertionSort ( int L[], const int begin, const int end)
027 {
028 //按关键码 Key 非递减顺序对表进行排序
029 int temp;
030 int i, j;
031 for ( i = begin; i < end; i++ )
032 {
033 if (L[i]>L[i+1])
034 {
035 temp = L[i+1];
036 j=i;
037 do
038 {
039 L[j+1]=L[j];
040 if(j == 0)
041 {
042 j--;
043 break;
044 }
045 j--;
046
047 } while(temp<L[j]);
048 L[j+1]=temp;
049 }
050 }
051 }
052 //n*logn
053 //快速排序A[startingsub],A[endingsub]都参与排序
054 void QuickSort( int A[], int startingsub, int endingsub)
055 {
056 if ( startingsub >= endingsub )
057 ;
058 else{
059 int partition;
060 int q = startingsub;
061 int p = endingsub;
062 int hold;
063
064 do{
065 for(partition = q ; p > q ; p--){
066 if( A[q] > A[p]){
067 hold = A[q];
068 A[q] = A[p];
069 A[p] = hold;
070 break;
071 }
072 }
073 for(partition = p; p > q; q++){
074 if(A[p] < A[q]){
075 hold = A[q];
076 A[q] = A[p];
077 A[p] = hold;
078 break;
079 }
080 }
081
082 }while( q < p );
083 QuickSort( A, startingsub, partition - 1 );
084 QuickSort( A, partition + 1, endingsub );
085 }
086 }
087
088 //希尔排序,L[left],L[right]都参与排序
089 void Shellsort( int L[], const int left, const int right)
090 {
091 int i, j, gap=right-left+1; //增量的初始值
092 int temp;
093 do{
094 gap=gap/3+1; //求下一增量值
095 for(i=left+gap; i<=right; i++)
096 //各子序列交替处理
097 if( L[i]<L[i-gap]){ //逆序
098 temp=L[i]; j=i-gap;
099 do{
100 L[j+gap]=L[j]; //后移元素
101 j=j-gap; //再比较前一元素
102 }while(j>left&&temp<L[j]);
103 L[j+gap]=temp; //将vector[i]回送
104 }
105 }while(gap>1);
106 }
107
108 //n
109 //计数排序,L[n]不参与排序
110 void CountingSort( int L[], const int n )
111 {
112 int i,j;
113 const int k =1001;
114 int tmp[k];
115 int *R;
116 R = new int[n];
117 for(i=0;i<k;i++) tmp[i]= 0;
118 for(j=0;j<n;j++) tmp[L[j]]++;
119 //执行完上面的循环后,tmp[i]的值是L中等于i的元素的个数
120 for(i=1;i<k;i++)
121 tmp[i]=tmp[i]+tmp[i-1]; //执行完上面的循环后,
122 //tmp[i]的值是L中小于等于i的元素的个数
123 for(j=n-1;j>=0;j--) //这里是逆向遍历,保证了排序的稳定性
124 {
125
126 R[tmp[L[j]]-1] = L[j];
127 //L[j]存放在输出数组R的第tmp[L[j]]个位置上
128 tmp[L[j]]--;
129 //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数
130
131 }
132 for(j=0;j<n;j++) L[j] = R[j];
133 }
134
135 //基数排序
136 void printArray( const int Array[], const int arraySize );
137 int getDigit(int num, int dig);
138 const int radix=10; //基数
139 void RadixSort(int L[], int left, int right, int d){
140 //MSD排序算法的实现。从高位到低位对序列划分,实现排序。d是第几位数,d=1是最低位。left和right是待排序元素子序列的始端与尾端。
141 int i, j, count[radix], p1, p2;
142 int *auxArray;
143 int M = 5;
144 auxArray = new int[right-left+1];
145 if (d<=0) return; //位数处理完递归结束
146 if (right-left+1<M){//对于小序列可调用直接插入排序
147 InsertionSort(L,left,right); return;
148 }
149 for (j=0; j<radix; j++) count[j]=0;
150 for (i=left; i<=right; i++) //统计各桶元素的存放位置
151 count[getDigit(L[i],d)]++;
152 for (j=1; j<radix; j++) //安排各桶元素的存放位置
153 count[j]=count[j]+count[j-1];
154 for (i=right; i>=left; i--){ //将待排序序列中的元素按位置分配到各个桶中,存于助数组auxArray中
155 j=getDigit(L[i],d); //取元素L[i]第d位的值
156 auxArray[count[j]-1]=L[i]; //按预先计算位置存放
157 count[j]--; //计数器减1
158 }
159 for (i=left, j=0; i<=right; i++, j++)
160 L[i]=auxArray[j]; //从辅助数组顺序写入原数组
161 delete []auxArray;
162 for (j=0; j<radix; j++){ //按桶递归对d-1位处理
163 p1=count[j]+left; //取桶始端,相对位置,需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
164 (j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端
165 // delete []count;
166 if(p1<p2){
167 RadixSort(L, p1, p2, d-1); //对桶内元素进行基数排序
168 // printArray(L,10);
169 }
170 }
171
172 }
173
174 int getDigit(int num, int dig)
175 {
176 int myradix = 1;
177 /* for(int i = 1;i<dig;i++)
178 {
179 myradix *= radix;
180 }*/
181 switch(dig)
182 {
183 case 1:
184 myradix = 1;
185 break;
186 case 2:
187 myradix = 10;
188 break;
189 case 3:
190 myradix = 1000;
191 break;
192 case 4:
193 myradix = 10000;
194 break;
195 default:
196 myradix = 1;
197 break;
198 }
199 return (num/myradix)%radix;
200 }
maintest.cpp 测试例子:
view sourceprint?001 #include<iostream>
002 using std::cout;
003 using std::cin;
004 using std::endl;
005 #include <cstdlib>
006 #include <ctime>
007 #include<iostream>
008 using std::cout;
009 using std::cin;
010 using std::ios;
011 using std::cerr;
012 using std::endl;
013 #include<iomanip>
014 using std::setw;
015 using std::fixed;
016 #include<fstream>
017 using std::ifstream;
018 using std::ofstream;
019 using std::flush;
020 #include<string>
021 using std::string;
022 #include <stdio.h>
023 #include <stdlib.h>
024 #include <time.h>
025 #include"minheap.h"
026 void BubbleSort(int arr[], int size);//冒泡排序
027 void QuickSort( int A[], int startingsub, int endingsub);//快速排序
028 void InsertionSort ( int L[], const int begin,const int n);//插入排序
029 void Shellsort( int L[], const int left, const int right);//希尔排序
030 void CountingSort( int L[], const int n );//计数排序
031 int getDigit(int num, int dig);//基数排序中获取第dig位的数字
032 void RadixSort(int L[], int left, int right, int d);//基数排序
033 void printArray( const int Array[], const int arraySize );//输出数组
034
035 int main()
036 {
037 clock_t start, finish;
038 double duration;
039 /* 测量一个事件持续的时间*/
040 ofstream *ofs;
041 string fileName = "sortResult.txt";
042 ofs = new ofstream(fileName.c_str(),ios::out|ios::app);
043 const int size = 100000;
044 int a[size];
045 int b[size];
046 srand(time(0));
047 ofs->close();
048 for(int i = 0; i < 20;i++)
049 {
050 ofs->open(fileName.c_str(),ios::out|ios::app);
051 if( ofs->fail()){
052 cout<<"!!";
053 ofs->close();
054 }
055
056 for(int k =0; k <size;k++)
057 {
058 a[k] = rand()%1000;
059 b[k] = a[k];
060
061 }
062 /* for( k =0; k <size;k++)
063 {
064 a[k] = k;
065 b[k] = a[k];
066
067 } */
068 //printArray(a,size);
069 //计数排序
070 for( k =0; k <size;k++)
071 {
072 a[k] = b[k];
073 }
074 start = clock();
075 CountingSort(a,size);
076
077 finish = clock();
078 // printArray(a,size);
079
080 duration = (double)(finish - start) / CLOCKS_PER_SEC;
081 printf( "%s%f seconds\n", "计数排序:",duration );
082 *ofs<<"第"<<i<<"次:\n " <<"排序内容:0~999共" << size << " 个整数\n" ;
083 *ofs<<"第"<<i<<"次计数排序:\n " <<" Time: " <<fixed<< duration << " seconds\n";
084 //基数排序
085 for( k =0; k <size;k++)
086 {
087 a[k] = b[k];
088 }
089 start = clock();
090 RadixSort(a, 0,size-1, 3);
091 finish = clock();
092 // printArray(a,size);
093
094 duration = (double)(finish - start) / CLOCKS_PER_SEC;
095 printf( "%s%f seconds\n", "基数排序:",duration );
096 *ofs<<"第"<<i<<"次基数排序:\n " <<" Time: " << duration << " seconds\n";
097 //堆排序
098 MinHeap<int> mhp(a,size);
099 start = clock();
100 for( k =0; k <size;k++)
101 {
102 mhp.RemoveMin(a[k]);
103 }
104 finish = clock();
105 // printArray(a,size);
106 duration = (double)(finish - start) / CLOCKS_PER_SEC;
107 printf( "%s%f seconds\n", "堆排序:",duration );
108 *ofs<<"第"<<i<<"次堆排序:\n " <<" Time: " << duration << " seconds\n";
109 //快速排序
110 for( k =0; k <size;k++)
111 {
112 a[k] = b[k];
113
114 }
115 //printArray(a,size);
116 start = clock();
117 QuickSort(a,0,size-1);
118 finish = clock();
119 // printArray(a,size);
120 duration = (double)(finish - start) / CLOCKS_PER_SEC;
121 printf( "%s%f seconds\n", "快速排序:",duration );
122 *ofs<<"第"<<i<<"次快速排序:\n " <<" Time: " << duration << " seconds\n";
123
124 //希尔排序
125 for( k =0; k <size;k++)
126 {
127 a[k] = b[k];
128 }
129 start = clock();
130 Shellsort(a,0,size-1);
131
132 finish = clock();
133 // printArray(a,size);
134
135 duration = (double)(finish - start) / CLOCKS_PER_SEC;
136 printf( "%s%f seconds\n", "希尔排序:",duration );
137 *ofs<<"第"<<i<<"次希尔排序:\n " <<" Time: " << duration << " seconds\n";
138
139 //插入排序
140 for( k =0; k <size;k++)
141 {
142 a[k] = b[k];
143 }
144 start = clock();
145 InsertionSort (a,0,size-1);
146 finish = clock();
147 // printArray(a,size);
148
149 duration = (double)(finish - start) / CLOCKS_PER_SEC;
150 printf( "%s%f seconds\n", "插入排序:",duration );
151 *ofs<<"第"<<i<<"次插入排序:\n " <<" Time: " << duration << " seconds\n";
152 //冒泡排序
153 for( k =0; k <size;k++)
154 {
155 a[k] = b[k];
156 }
157 start = clock();
158 BubbleSort(a,size);
159 finish = clock();
160 // printArray(a,size);
161
162 duration = (double)(finish - start) / CLOCKS_PER_SEC;
163 printf( "%s%f seconds\n", "冒泡排序:",duration );
164 *ofs<<"第"<<i<<"次冒泡排序:\n " <<" Time: " << duration << " seconds\n";
165
166 ofs->close();
167 }
168 return 0;
169 }
170
171 void printArray( const int Array[], const int arraySize )
172 {
173 for( int i = 0; i < arraySize; i++ ) {
174 cout << Array[ i ] << " ";
175 if ( i % 20 == 19 )
176 cout << endl;
177 }
178 cout << endl;
179 }
排序算法性能仿真:
排序内容:从0~999中随机产生,共100000 个整数,该表中单位为秒。
次数 计数排序 基数排序 堆排序 快速排序 希尔排序 直接插入排序 冒泡排序
1 0.0000 0.0310 0.0470 0.0470 0.0310 14.7970 58.0930
2 0.0000 0.0470 0.0310 0.0470 0.0470 16.2500 53.3280
3 0.0000 0.0310 0.0310 0.0310 0.0310 14.4850 62.4380
4 0.0000 0.0320 0.0320 0.0470 0.0310 17.1090 61.8440
5 0.0000 0.0310 0.0470 0.0470 0.0310 16.9380 62.3280
6 0.0000 0.0310 0.0310 0.0470 0.0310 16.9380 57.7030
7 0.0000 0.0310 0.0470 0.0310 0.0310 16.8750 61.9380
8 0.0150 0.0470 0.0310 0.0470 0.0320 17.3910 62.8600
9 0.0000 0.0320 0.0470 0.0460 0.0310 16.9530 62.2660
10 0.0000 0.0470 0.0310 0.0470 0.0310 17.0160 60.1410
11 0.0000 0.0930 0.0780 0.0320 0.0310 14.6090 54.6570
12 0.0000 0.0310 0.0320 0.0310 0.0310 15.0940 62.3430
13 0.0000 0.0310 0.0310 0.0470 0.0310 17.2340 61.9530
14 0.0000 0.0320 0.0470 0.0470 0.0310 16.9060 61.0620
15 0.0000 0.0320 0.0320 0.0460 0.0320 16.7810 62.5310
16 0.0000 0.0470 0.0470 0.0620 0.0310 17.2350 57.1720
17 0.0150 0.0160 0.0320 0.0470 0.0310 14.1400 52.0320
18 0.0150 0.0160 0.0310 0.0310 0.0310 14.1100 52.3590
19 0.0000 0.0310 0.0320 0.0460 0.0320 14.1090 51.8750
20 0.0000 0.0310 0.0320 0.0460 0.0320 14.0780 52.4840
21 0.0150 0.0780 0.0470 0.0470 0.0310 16.3750 59.5150
22 0.0000 0.0310 0.0310 0.0470 0.0320 16.8900 60.3440
23 0.0000 0.0310 0.0310 0.0310 0.0310 16.3440 60.0930
24 0.0000 0.0310 0.0310 0.0470 0.0310 16.3440 60.5780
25 0.0000 0.0320 0.0470 0.0470 0.0470 16.3590 59.7810
26 0.0160 0.0470 0.0310 0.0470 0.0310 16.1250 61.0620
27 0.0000 0.0310 0.0470 0.0470 0.0310 16.7810 59.6100
28 0.0150 0.0320 0.0320 0.0470 0.0310 16.9220 56.8130
29 0.0000 0.0310 0.0310 0.0310 0.0310 15.0790 57.8120
30 0.0000 0.0310 0.0320 0.0460 0.0320 14.7810 58.8280
31 0.0000 0.0310 0.0310 0.0470 0.0310 15.8590 59.1400
32 0.0000 0.0470 0.0320 0.0310 0.0310 16.0940 59.1560
33 0.0000 0.0470 0.0310 0.0310 0.0310 15.9850 59.1400
34 0.0000 0.0310 0.0310 0.0470 0.0320 16.0150 59.2500
35 0.0000 0.0310 0.0470 0.0470 0.0310 16.7660 57.9840
36 0.0000 0.0310 0.0320 0.0470 0.0310 15.3750 59.0470
37 0.0000 0.0320 0.0460 0.0470 0.0320 16.0310 58.9060
38 0.0000 0.0310 0.0310 0.0470 0.0310 15.9530 57.2650
39 0.0160 0.0310 0.0470 0.0470 0.0310 15.9530 57.5160
40 0.0150 0.0310 0.0320 0.0470 0.0310 14.7030 56.6710
平均值 0.0031 0.0360 0.0372 0.0437 0.0320 15.9946 58.7480
最小值 0.0000 0.0160 0.0310 0.0310 0.0310 14.0780 51.8750
最大值 0.0160 0.0930 0.0780 0.0620 0.0470 17.3910 62.8600
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 673在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 700最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1087在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3074输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1034背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1293我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 700Problem 1 : Is it a loop ? ( ... -
背包问题之硬币找零问题
2011-08-25 19:19 1177设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1374求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 758题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1325题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1827题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1061很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 602给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 967在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 761快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 745乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 795最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1043阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 随机产生空间大小为: N = 10, 1000,10000,100000 的排序样本,取值为[0,1]区间 输出: 1) N=10时,排序结果。 2) N=1000,10000,...
本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型的排序算法以及它们的C++实现,还有可能的可视化演示,帮助理解每种算法的工作原理。 首先,让我们逐一了解常见的排序...
"各种排序算法时间性能的比较"这个程序文件可能是用C++语言实现的,C++以其高效和灵活性成为实现算法的常用语言。在这个程序中,应该包含了各种排序算法的函数实现,并且有一个主程序用于测试和比较这些排序算法的...
冒泡排序是一种基础的排序算法,它通过重复遍历待排序的序列,比较相邻元素并交换位置,使得每个元素都能逐步“浮”到正确的位置上。在这个过程中,最大(或最小)的元素会像气泡一样逐渐上升到序列的顶端。这种算法...
综上所述,"插入排序算法c++实现"涉及到C++基础语法、数组与指针操作、循环和条件控制、排序算法原理、性能分析以及良好的编程习惯等多个方面。通过实践这个项目,开发者不仅可以深入理解插入排序算法,还能提升C++...
### 各种排序算法的C++模板类实现 本文将详细介绍一种C++模板类实现的各种排序算法,包括快速排序、选择排序、冒泡排序、插入排序、堆排序以及二叉排序树排序。这些算法在数据结构与算法领域非常重要,被广泛应用于...
在IT领域,排序算法是计算机科学中的基础但至关重要的部分,尤其在编程语言如C++中,理解并能熟练运用各种排序算法对于提升程序效率至关重要。以下是对标题和描述中涉及的主要排序算法的详细解释: 1. **插入类排序...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法。 A 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的排序样本(取值为[0,1])上测试以上算法。 B.结果输出: 1) N=10时,...
通过阅读和分析这些代码,可以深入理解各种排序算法的内部工作原理,以及如何在不同层面(软件和硬件)实现它们。同时,这也为优化排序算法提供了实践机会,比如在特定硬件平台上优化性能,或者在保证正确性的前提下...
在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在C++这样的系统级编程语言中,理解和掌握各种排序算法的实现至关重要。这里我们将深入探讨标题中提到的五种排序算法——归并排序、快速排序、希尔排序...
内排序是计算机科学中一...在数据结构第十章的实验中,学习和比较这些排序算法有助于理解它们的工作原理、性能特征和适用场景。通过编写和测试这些算法,可以加深对排序问题的理解,并为实际编程项目提供有价值的工具。
这些排序算法在C++中实现时,通常会利用C++的模板机制,使其能够适用于各种数据类型。同时,为了提高效率,可能会采用STL中的迭代器进行操作,以及考虑内存管理、异常安全性和性能优化等高级主题。在实际开发中,...
各种排序算法性能的比较 在计算机科学中,排序算法是将一组数据按照一定的顺序排列的过程。排序算法的性能直接影响到数据处理和分析的效率。本课程设计中,我们将对八种内部排序算法的性能进行分析和比较。 1. ...
本文将深入探讨在C++中实现的各种排序算法,包括它们的工作原理、效率以及如何用C++代码来表达。 首先,我们来看直接插入排序。这种排序算法的工作方式类似于我们手动排列一副扑克牌,每次将一个未排序的元素插入到...
在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在C++这样的系统级编程语言中,理解和掌握各种排序算法至关重要。本资源包包含了C++实现的选择排序、快速排序、堆排序、冒泡排序以及Shell排序这五种...
标题中的"C++实现各种排序算法排序性能的比较"指出,这是一个关于C++编程的项目,其核心内容是对比不同排序算法的效率。排序是计算机科学中的基础问题,它在数据分析、数据库管理等领域有着广泛的应用。C++作为一种...
这个压缩包文件"各种经典排序算法C++/C"显然包含了多种使用C++和C语言实现的排序算法。以下是对这些算法的详细介绍: 1. **冒泡排序**(Bubble Sort):冒泡排序是最基础的排序算法之一,通过重复遍历待排序的数列...
本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...
总的来说,这个压缩包"**C++实现各种排序算法.zip**"为我们提供了一个宝贵的资源库,可以帮助我们学习和比较不同排序算法的实现,从而提升编程技能,更好地解决实际问题。通过阅读和分析这些代码,我们可以深入理解...