2013-08-22 14:55:33

八大排序方法汇总（选择排序-简单选择排序、堆排序，插入排序-简单插入排序、shell排序，交换排序-冒泡排序、快速排序，归并排序，计数排序）。

插入排序还可以和折半查找相结合，提高查找插入位置的速度，也就是折半插入排序，此处没有给出这种方法的相应代码。

对排序算法，可从以下几个方面评价：

1. 时间复杂度；
2. 空间复杂度；
3. 稳定性。

 

代码（测试暂未发现问题，欢迎交流指正！）：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 typedef int DataType;  8 const int MaxSize = 1000000;  9 const int SortCutOff = 50; 10  11 //产生在[lowBound,upperBound - 1]区间的随机数 12 int RandomIntGenerate(int lowBound, int upperBound) 13 {     14     return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + 1) ); 15 } 16  17  18 //数组显示 19 void DisplayArray(DataType array[],int len) 20 { 21     assert(NULL != array && len > 0); 22  23     for (int i = 0;i < len;++i) 24     { 25         cout<
         
          <<"\t"; 26     } 27     cout<
          
            0); 34 35 size_t i; 36 size_t j; 37 size_t minIndex = 0; 38 39 for (i= 0;i < n - 1;++i) 40 { 41 minIndex = i; 42 for (j = i + 1;j < n;++j) 43 { 44 minIndex = unStorted[minIndex] < unStorted[j] ? minIndex : j; 45 } 46 47 swap(unStorted[i],unStorted[minIndex]); //没有判断i与minIndex是否相等 48 } 49 } 50 51 //简单插入排序 52 void InsertSort(DataType *unStorted,size_t n) 53 { 54 assert(NULL != unStorted && n > 0); 55 56 size_t i; 57 int j; //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件 58 DataType dataToInsert = 0; 59 60 for (i= 0;i < n - 1;++i) 61 { 62 dataToInsert = unStorted[i + 1]; 63 for (j = i;j >= 0;--j) 64 { 65 if (unStorted[j] > dataToInsert) 66 { 67 unStorted[j + 1] = unStorted[j]; 68 } 69 else 70 { 71 break; 72 } 73 } 74 unStorted[j + 1] = dataToInsert; //注意此处为j + 1，而非j 75 } 76 } 77 78 //插入排序-shell排序 79 //简单插入排序在输入为基本有序的情况下，性能最好， 80 //shell排序每次大步长下的排序，相当于通过分组对数组预处理，使其基本有序 81 void ShellSort(DataType *unStorted,size_t n) 82 { 83 assert(NULL != unStorted && n > 0); 84 85 size_t step = n / 2; 86 size_t k; 87 size_t i; 88 int j; //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件 89 DataType dataToInsert = 0; 90 91 while (step >= 1) //n为1时，step为0，不进入while循环就返回； 92 { 93 for (k = 0;k < step;++k ) 94 { 95 for (i= 0;i < n - step;i += step) 96 { 97 dataToInsert = unStorted[i + step]; 98 for (j = i;j >= 0;j -= step) 99 {100 if (unStorted[j] > dataToInsert)101 {102 unStorted[j + step] = unStorted[j];103 }104 else105 {106 break;107 }108 }109 unStorted[j + step] = dataToInsert; //注意此处为j + 1，而非j110 }111 }112 step /= 2; 113 }114 }115 116 //交换排序-冒泡排序117 void BubbleSort(DataType *unStorted,size_t n)118 {119 assert(NULL != unStorted && n > 0);120 121 size_t i;122 size_t j; 123 124 for (i = n - 1;i >= 1;--i)125 {126 for (j = 0;j < i;++j)127 {128 if (unStorted[j] > unStorted[j + 1])129 {130 swap(unStorted[j],unStorted[j + 1]);131 }132 }133 }134 }135 136 //快速排序的划分函数137 size_t Partion(DataType *unStorted,size_t begin,size_t end)138 {139 assert(begin <= end); //begin end都是定义为size_t的，因此不需要检查140 141 size_t i = begin;142 size_t j = end;143 //size_t pivot = i;144 size_t pivot = RandomIntGenerate(begin,end); //枢轴为随机的，使得快速排序的划分尽可能对称145 swap(unStorted[i],unStorted[pivot]);146 147 while (i < j)148 {149 while (j > i && unStorted[j] > unStorted[i])150 {151 --j;152 }153 154 if (j > i)155 {156 swap(unStorted[i],unStorted[j]);157 pivot = j;158 ++i;159 }160 161 while (i < j && unStorted[i] < unStorted[j])162 {163 ++i;164 }165 166 if (j > i)167 {168 swap(unStorted[i],unStorted[j]);169 pivot = i;170 --j;171 }172 }173 //return i;174 //return j;175 return pivot;176 }177 178 //交换排序-快速排序179 void QuickSort(DataType *unStorted,size_t begin,size_t end)180 {181 assert(NULL != unStorted);182 183 //assert(begin >= 0 && end >= 0); //begin end都是定义为size_t的，因此不需要检查184 185 if (begin >= end)186 {187 return;188 }189 190 int mid = Partion(unStorted,begin,end); 191 192 if (begin < mid)193 {194 QuickSort(unStorted,begin,mid - 1);195 }196 197 //QuickSort(unStorted,begin,mid - 1); //若mid为0，size_t类型的mid减1会出问题，因此用begin < mid判断198 QuickSort(unStorted,mid + 1,end);199 }200 201 //归并两个数组202 void Merge(DataType *unStorted,size_t begin,size_t mid,size_t end)203 {204 assert(NULL != unStorted);205 assert(begin <= mid && mid <=end);206 207 DataType *resArray = new DataType[end - begin + 1];208 DataType *res = resArray;209 210 size_t lowIndex = begin;211 size_t highIndex = mid + 1;212 213 while (lowIndex <= mid && highIndex <= end)214 {215 if (unStorted[lowIndex] <= unStorted[highIndex])216 {217 *res++ = unStorted[lowIndex++];218 }219 else220 {221 *res++ = unStorted[highIndex++];222 }223 }224 225 while (lowIndex <= mid)226 {227 *res++ = unStorted[lowIndex++];228 }229 230 while (highIndex <= end)231 {232 *res++ = unStorted[highIndex++];233 }234 235 res = resArray;236 237 for (size_t index = begin;index <= end;++index)238 {239 unStorted[index] = *res++;240 }241 242 delete [] resArray;243 }244 245 //归并排序的非递归实现，自底向上归并246 void MergeSortNonRecursive(DataType *unStorted,size_t n)247 {248 assert(NULL != unStorted);249 250 size_t begin = 0;251 size_t mid = 0;252 size_t end = 0;253 254 size_t step = 1;255 256 while (step < n)257 {258 begin = 0;259 mid = begin + step - 1;260 end = begin+ 2 * step - 1;261 262 while (mid < n)263 {264 end = end > (n - 1) ? (n - 1) : end; //防止end越界265 266 Merge(unStorted,begin,mid,end);267 268 begin = end + 1; //不是begin = begin + step + 1;269 mid = begin + step - 1;270 end = begin+ 2 * step - 1;271 }272 step *= 2;273 }274 }275 276 //归并排序的非递归实现，自顶向下归并，分治法277 void MergeSort(DataType *unStorted,size_t begin,size_t end)278 {279 assert(NULL != unStorted);280 281 if (begin >= end)282 {283 return;284 }285 286 size_t mid = begin + (end - begin) / 2;287 MergeSort(unStorted,begin,mid);288 MergeSort(unStorted,mid + 1,end); //若mid为size_t类型最大值，mid + 1就会越界，此时end已经越界289 Merge(unStorted,begin,mid,end);290 }291 292 //堆调整293 //参数n为数组中最大小标，如数组有n+1个元素，最大下标为n294 //posToAdjust为需要调整的位置的下标295 void HeapAdjust(DataType *unStorted,size_t n,size_t posToAdjust)296 {297 assert(NULL != unStorted); //在调用的函数中已经有，可以删去298 299 size_t lchildIndex = 2 * posToAdjust + 1;300 size_t rchildIndex = 2 * posToAdjust + 2;301 302 size_t maxPosition = posToAdjust;303 304 //while (lchildIndex <= n || rchildIndex <= n)305 while (lchildIndex <= n) //此处只要lchildIndex <= n ，即可进入循环306 {307 if (lchildIndex <= n && unStorted[lchildIndex] > unStorted[maxPosition])308 {309 maxPosition = lchildIndex;310 }311 //else if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition])312 if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition]) //不是else if 313 {314 maxPosition = rchildIndex;315 }316 317 if (maxPosition != posToAdjust)318 {319 swap(unStorted[posToAdjust],unStorted[maxPosition]);320 321 posToAdjust = maxPosition; //更新posToAdjust，可以用递归，即HeapAdjust(unStorted,n,maxPosition);322 lchildIndex = 2 * maxPosition + 1;323 rchildIndex = 2 * maxPosition + 2;324 }325 else326 {327 break;328 }329 }330 }331 332 //堆排序333 //参数n为数组中最大小标，如数组有n+1个元素，最大下标为n334 void HeapSort(DataType *unStorted,size_t n)335 {336 assert(NULL != unStorted);337 338 int index;339 340 for (index = (n - 1) / 2;index >= 0;--index) //index需要减到0，因此不能定义为size_t341 {342 HeapAdjust(unStorted,n,index);343 }344 345 for (index = n;index >= 1;--index)346 {347 swap(unStorted[0],unStorted[index]);348 HeapAdjust(unStorted,index - 1,0); //不是HeapAdjust(unStorted,index,0);349 }350 }351 352 //计数排序，基本实现353 //此处的基数排序的使用场合：354 //输入为正数；355 // 输入不重复；356 //输入的最大数与输入的个数基本相等时空间利用率最高，也就是输入为0~n内的n个不重复的正数357 void CountSortBasic_1(DataType *unStorted,size_t n)358 {359 assert(NULL != unStorted);360 361 size_t *hash = new size_t [n + 1];362 size_t cnt = 0;363 int index = 0;364 365 for (index = 0;index <= n;++index)366 {367 hash[index] = 0;368 }369 370 for (index = 0;index < n;++index) //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1371 {372 ++hash[ unStorted[index] ];373 }374 375 for (index = 0;index <= n;++index)376 {377 if (hash[ index ] != 0) //判断index是否出现378 {379 unStorted[cnt++ ] = index; 380 }381 }382 383 delete [] hash;384 }385 386 //计数排序，位图实现387 void CountSort(DataType *unStorted,size_t n)388 {389 assert(NULL != unStorted);390 391 bitset
           
             hash;392 393 size_t cnt = 0;394 int index = 0;395 396 hash.reset();397 398 for (index = 0;index < n;++index) //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1399 {400 hash.set(unStorted[index]);401 }402 403 for (index = 0;index <= n;++index)404 {405 if ( hash.test(index) )406 {407 unStorted[cnt++ ] = index; 408 }409 }410 }411 412 //测试“脚手架”413 void TestSortDriver()414 { 415 /*DataType *unsortedArray = new DataType[MaxSize];416 size_t lengthOfUnsortedArray;*/417 size_t programToTest;418 419 int MinRandomInt;420 int MaxRandomInt;421 size_t i;422 int timeStart = 0;423 double timeCostAverage = 0;424 425 //用于计数排序时的输入426 DataType unsortedArray[10]= { 2,0,9,8,4,5,3,7,1,6};427 size_t lengthOfUnsortedArray = 10;428 429 430 cout<<"please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :"<
            
             >lengthOfUnsortedArray>>MinRandomInt>>MaxRandomInt;432 cout<<"please enter the identifier of the program to test (end with ctrl+z): "<
             
              >programToTest)434 {435 for (i = 0;i < lengthOfUnsortedArray;++i) //准备待排序数组436 {437 unsortedArray[i] = RandomIntGenerate(MinRandomInt,MaxRandomInt);438 }439 440 cout<<"the unsorted array is :"<
              
               < lengthOfUnsortedArray - 1;++i)500 {501 if (unsortedArray[i] > unsortedArray[i + 1])502 {503 cout<<"sort bug i = "<
               <