devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

四种排序的实现：冒泡、插入、归并、快速_冒泡排序:o{n2} 从后往前,两两比较换位

作者：你好赵伟 | 2024-04-23 19:46:56

赞

踩

冒泡排序:o{n2} 从后往前,两两比较换位

冒泡排序：O{n2}  从后往前，两两比较换位

选择排序：O(n2) 选择最小的，与最前面的换位

插入排序：O(n2) 从前往后，两两比较换位

堆排序： O(nlogn) 使用树结构，树顶点最大，取出后重新排列剩余树。

归并排序：O(nlogn) 分两组，在组内继续细分两组，直到一个为一组，然后比较相邻两组，比较换位

快速排序：O(nlogn) 找基准值，分左右两侧，左侧比基准小，右侧比基准大，在两侧内继续执行快速排序。

冒泡排序：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. void bubbleSort1(int list[], int length){
  6.     if (list == NULL){
  7.         cout << "list is null, return;";
  8.         return ;
  9.     }
  10.     cout << "bubble sort, list length="<< length<<endl;
  11.     for (int h = 0; h < length; h++){
  12.         cout << list[h] << "\t";
  13.     }
  14.     cout <<endl;
  15.     int temp;
  16.     bool swapped = true;
  17.     int runCount = 0;
  18.     for (int j = 0; j < length && swapped; j++){
  19.         swapped = false;
  20.         for (int i = length - 1; i > 0 && (j == 0 || list[i] > list[j-1]); i--){
  21.                 cout << runCount++ <<" ";
  22.                 if (list[i] < list[i-1]){
  23.                     temp = list[i];
  24.                     list[i] = list[i-1];
  25.                     list[i-1] = temp;
  26.                     swapped =true;
  27.                 }
  28.         }
  29.         cout <<endl<< "run "<< j+1 <<"th round: \t";
  30.         for (int k = 0; k < length; k++){
  31.             cout  << "\t" << list[k] ;
  32.         }
  33.         cout <<endl;
  34.     }
  35.         cout <<endl;
  36.         cout <<endl;
  37.         cout <<endl;
  38. }
  39.  
  40. int bubbleSort2(int* list, int length){
  41.     if (list == NULL || length < 2){
  42.         cout << " list is NULL, or not need to sort!" <<endl;
  43.         return -1;
  44.     }
  45.     int temp;
  46.     int shouldRun = true;
  47.     int swapPosition = 0;
  48.     int len = length - 1;
  49.     int runCount = 0;
  50.     for (int i = 0; shouldRun && i < length; i++){
  51. 	    int* tempList = list;
  52.         shouldRun = false;
  53.         for (int j=0; j < len; j ++){
  54.             cout << runCount++ <<" ";
  55.             if (*tempList > *(tempList + 1)){
  56.                 temp = *tempList;
  57.                 *tempList = *(tempList + 1);
  58.                 *(tempList + 1) = temp;
  59.                 shouldRun = true;
  60.                 swapPosition = j;
  61.             }
  62.             tempList ++;
  63.         }
  64.         len = swapPosition;
  65.         cout <<endl<< "run "<< i+1 <<"th round: \t";
  66.         for (int k = 0; k < length; k++){
  67.             cout  << "\t" << *(list+k) ;
  68.         }
  69.         cout <<endl;
  70.     }
  71.     return 0;
  72. }
  73.  
  74.  
  75. int main(){
  76. //    int list[10] = {0,9,8,7,6,5,4,3,2,1};
  77.     int list[10] = {9,8,7,6,5,4,3,2,1, 0};
  78. //    int list[10] =  NULL;
  79. /*
  80.     cout << "please input 10 number to sort!" << endl;
  81.     for(int j = 0; j<10;j++){
  82.         cin >> list[j] ;
  83.     }
  84. */
  85.     bubbleSort1(list, sizeof(list)/sizeof(list[0]));
  86. //    int list1[10] = {9,8,7,6,5,4,3,2,1,0};
  87. //    int list1[10] = {0,0,0,0,0,0,0,0,0,0};
  88.     int list1[10] = {0,0,0,0,0,1,0,0,0,0};
  89.     bubbleSort2(list1, sizeof(list1)/sizeof(list1[0]));
  90.  
  91.     cout <<" Sorted number list is ";
  92.     for (int i = 0; i < 10; i++){
  93.        cout << list[i] << "\t";
  94.     }
  95.  
  96.     cout <<endl;
  97.     return 0;
  98. }

插入排序：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int insertSort(int array[], int length);
  6. void print(int array[], int length);
  7. int swapValue(int& a, int& b, int& temp);
  8.  
  9. int main(){
  10.     int array[] = {9,8,7,6,5,4,3,2,1,0};
  11.     int length = sizeof(array)/sizeof(array[0]);
  12.     insertSort(array, length);
  13.     print(array, length);
  14.     return 0;
  15. }
  16.  
  17. int insertSort(int array[], int length){
  18.  
  19.     if (array == NULL || length < 2){
  20.         return -1;
  21.     }
  22.     int temp;
  23.     for (int i = 0; i < length; i++){
  24.         for (int j = i; j > 0 && array[j] < array[j-1]; j--){
  25.             swapValue(array[j], array[j-1], temp);
  26.         }
  27.  
  28.     }
  29.  
  30.     return 0;
  31. }
  32.  
  33.  
  34. int swapValue(int& a, int& b, int& temp){
  35.     temp = a;
  36.     a = b;
  37.     b = temp;
  38.     return 0;
  39. }
  40. void print(int array[], int length){
  41.  
  42.     cout<<endl<< "print array, length="<<length<<endl;
  43.     for(int i = 0; i< length;i++){
  44.         cout<<"\t"<<array[i];
  45.     }
  46.     cout<<endl;
  47. }
  48.

归并排序：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int mergeSort(int array[], int length);
  6. void print(int array[], int length);
  7. int swapValue(int& a, int& b, int& temp);
  8. int doMerge(int* a, int leftLength, int* b, int rightLength);
  9.  
  10. int count = 1;
  11.  
  12. int main(){
  13.     int array[] = {9,8,7,6,5,4,3,2,1,0};
  14. //    int array[] = {9,8};
  15.     int length = sizeof(array)/sizeof(array[0]);
  16.     mergeSort(array, length);
  17.     print(array, length);
  18.     return 0;
  19. }
  20. int mergeSort(int array[], int length){
  21.     if (array == NULL || length <2){
  22.         return -1;
  23.     }
  24.     int subLength = length / 2;
  25.     doMerge(array, subLength, array + subLength, length - subLength);
  26.     return 0;
  27. }
  28. int doMerge(int* a, int leftLength, int* b, int rightLength){
  29.     if (a == NULL || b == NULL){
  30.         cout<<" array is null, please check!"<<endl;
  31.         return -1;
  32.     }
  33.     int temp;
  34. //    cout << "leftL="<<leftLength << " rightL="<<rightLength << endl;
  35.     if (leftLength == 1 && rightLength == 1){
  36.         cout <<endl<<count++<< " swap:"<<*a<<"--"<<*b<<endl;
  37.         swapValue(*a, *b, temp);
  38.         return true;
  39.     }
  40.     if (leftLength > 1){
  41.         int subLLength = leftLength / 2;
  42.         doMerge(a, subLLength, a + subLLength, leftLength - subLLength);
  43.     }
  44.     if (rightLength > 1){
  45.         int subRLength = rightLength / 2;
  46.         doMerge(b, subRLength, a + subRLength, rightLength - subRLength);
  47.     }
  48.     for (int i = 0; i < rightLength; i++){
  49.         for (int j = leftLength - 1; j >= 0; j--){
  50.             if (*(a+i) > *(b+j)){
  51.                 cout <<endl<<count++<< " swap:"<<*(a+i)<<"--"<<*(b+j)<<endl;
  52.                 swapValue(*(a+i), *(b+j), temp);
  53.             }
  54.         }
  55.     }
  56.     return 0; 
  57. }
  58.  
  59. void print(int array[], int length){
  60.  
  61.     cout<<endl<< "print array, length="<<length<<endl;
  62.     for(int i = 0; i< length;i++){
  63.         cout<<"\t"<<array[i];
  64.     }
  65.     cout<<endl;
  66. }
  67. int swapValue(int& a, int& b, int& temp){
  68.     temp = a;
  69.     a = b;
  70.     b = temp;
  71.     return 0;
  72. }

快速排序：

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void print(int list[], int length);
  5. void print(int i, int j, int& runCount, int list[],  int length);
  6. int swapValue(int& a, int& b);
  7. int quickSort2(int* list, int length);
  8. int quickSort3(int list[], int low, int high);
  9. int runQuickSort(int list[], int low, int high);
  10. int runQuickSort2(int list[], int low, int high);
  11.  
  12.  
  13.  
  14.  
  15. int main(){
  16. //    int list1[] = {9,2,5,1,8,7,0,6,3,4};
  17.     int list1[] = {0,1,2,3,4,5,6,7,8,9};
  18. //    int list1[] = {9,8,7,6,5,4,3,2,1,0};
  19. //    int list1[] = {3,2,0,1,4};
  20.  
  21.     int length = sizeof(list1)/sizeof(list1[0]);
  22. //    quickSort2(list1, length);
  23.     quickSort3(list1, 0, length - 1);
  24.  
  25.     cout <<endl<<"quick sort list: ";
  26.     for (int h = 0; h< length; h++){
  27.         cout << "\t"<<list1[h];
  28.     }
  29.     cout <<endl;
  30.     return 0;
  31. };
  32.  
  33. int quickSort2(int* list, int length){
  34.     if (list == NULL || length < 2){
  35.         return -1;
  36.     }
  37.     int temp;
  38.     int* runList = list;
  39.     int compare = *(runList + length - 1);
  40.     int last = length - 2;
  41.     int changePosition = -1;
  42. //    cout <<endl<<"quick sort2: "<< length << " compare:"<< compare<<endl;
  43. //    print(list, length);
  44.     for (int i = 0; i <= last; i ++){
  45.         if (*(runList+i) > compare){
  46.             for (; last > i; last --){
  47.                 if(*(runList+last) < compare){
  48.                     swapValue(*(runList + i), * (runList + last));
  49.                     break;
  50.                 }
  51.             }
  52.         }
  53.         changePosition = i;
  54.     }
  55.  
  56. //    cout <<endl<<"quick sort2: "<< length << " changePosition:"<< changePosition <<endl;
  57.  
  58.     if (changePosition > -1 && changePosition < length){
  59.         swapValue(*(list+changePosition), *(list+ + length - 1));
  60.     }
  61.     if(changePosition > 1 && changePosition < length){
  62.         cout << "left side: "<<endl;
  63.         print(list, changePosition);
  64.         quickSort2(list, changePosition);
  65.     }
  66.     if (changePosition > -1 && changePosition < length - 2){
  67.         cout << "right side: "<<endl;
  68.         print(list + changePosition + 1, length - changePosition - 1);
  69.         quickSort2(list + changePosition + 1, length - changePosition - 1);
  70.  
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
  76. int quickSort3(int list[], int low, int high){
  77.  
  78.     if(low < high){
  79. //        int comparePosition = runQuickSort(list, low, high);
  80.         int comparePosition = runQuickSort2(list, low, high);
  81. cout<<endl<<"run begin:::";
  82.  
  83.     for(int h = low; h <high+1; h++){
  84.         cout <<"\t"<<list[h];
  85.     }
  86. //        if (comparePosition > low + 1 && comparePosition < high){
  87. cout<<endl<<"left left ccc="<<comparePosition<<endl;
  88.             quickSort3(list, low, comparePosition -1);
  89. //        }
  90. //        if (comparePosition > low && comparePosition < high - 1){
  91. cout<<endl<<"right right cccc==="<<comparePosition<<endl;
  92.             quickSort3(list, comparePosition + 1, high);
  93. //        }
  94.     }
  95.  
  96.  
  97.     return 0;
  98. }
  99.  
  100.  
  101. int runQuickSort(int list[], int low, int high){
  102.     if (list != NULL && high <= low){
  103.        return low;
  104.     }
  105.     cout <<endl<<"run quick sort begion " <<endl;
  106.     for(int h = low; h <high+1; h++){
  107.         cout <<"\t"<<list[h];
  108.     }
  109.     int i = low;
  110.     int j = high - 1;
  111.     int compareValue = list[high];
  112.     while(i <= j){
  113.         if (list[i] > compareValue){
  114.             while(j > i){
  115.                 if (list[j] < compareValue){
  116.                     swapValue(list[i], list[j]);
  117.                     break;
  118.                 }
  119.                 j--;
  120.             }
  121.         }
  122.         cout << endl << "i="<<i<<" j="<<j<<endl;
  123.         if (i == j){
  124.             swapValue(list[i],list[high]);
  125.             cout <<endl<<"swap comapre is : "<<"i = "<<i <<"; value="<<list[i] << ", high value:"<< list[high] <<endl;
  126.             break;
  127.         }
  128.         i++;
  129.     }
  130.     cout <<endl<<"run quick sort end,: "<<compareValue <<endl;
  131.     for(int h = low; h <high+1; h++){
  132.         cout <<"\t"<<list[h];
  133.     }
  134.     return i;
  135.  
  136. }
  137.  
  138. int runQuickSort2(int list[], int low, int high){
  139.     int key = list[low];
  140.     cout <<"run sort begin:   low ="<<low<<" high="<<high<<" key="<<key<<endl;
  141.     while(low < high){
  142.         while (low < high && list[high] >= key){
  143.             high --;
  144.         }
  145.         if (low < high){
  146.             list[low] = list[high];
  147.         }
  148.         while(low < high && list[low] <=  key){
  149.             low++;
  150.         }
  151.         if (low < high){
  152.             list[high] = list[low];
  153.         }
  154.     }
  155.     list[low] = key;
  156.     return low;
  157. }
  158.  
  159. int swapValue(int& a, int& b){
  160.  
  161. int temp = a;
  162. a = b;
  163. b = temp;
  164. return 0;
  165. }
  166. void print(int list[], int length){
  167.                     for (int h = 0; h< length; h++){
  168.                         cout << "\t"<<list[h];
  169.                     }
  170.                     cout <<endl;
  171.  
  172. }
  173. void print(int i, int j, int& runCount, int list[], int length){
  174.                     cout <<"run count: "<< runCount++ <<"\t" << i<<" "<<j;
  175.                     cout <<endl;
  176.                     cout <<endl;
  177.                     for (int h = 0; h< length; h++){
  178.                         cout << "\t"<<list[h];
  179.                     }
  180.                     cout <<endl;
  181. }
  182.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/475718
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号