fork download
copy 
  1. #include<iostream>
  2. #include<stdlib.h> 
  3. #include<stdio.h>
  4. #include<string.h>
  5.  
  6. using namespace std;
  7.  
  8. void DisplayArray(int* a, int n) {
  9.     cout << "The elements in the array a[] are: \n";
  10.     for (int i = 0; i < n; i++)
  11.         cout << a[i] << " ";
  12.     cout << endl;
  13. }
  14.  
  15. void BubbleSort(int* a, int n) {
  16.     for (int i = 0; i <= n - 2; i++) {
  17.         for (int j = 0; j <= n - 2 - i; j++) {
  18.             if (a[j] > a[j + 1]) {
  19.                 int tmp = a[j];
  20.                 a[j] = a[j + 1];
  21.                 a[j + 1] = tmp;
  22.             }
  23.         }
  24.     }
  25. }
  26.  
  27. void EfficientBubbleSort(int* a, int n) {
  28.     for (int i = 0; i <= n - 2; i++) {
  29.         bool flag = false;
  30.         for (int j = 0; j <= n - 2 - i; j++) {
  31.             if (a[j] > a[j + 1]) {
  32.                 flag = true;
  33.                 int tmp = a[j];
  34.                 a[j] = a[j + 1];
  35.                 a[j + 1] = tmp;
  36.             }
  37.         }
  38.         if (flag == false) {
  39.             break;
  40.         }
  41.     }
  42. }
  43.  
  44. void InsertionSort(int* a, int n) {
  45.     for (int i = 1; i <= n - 1; i++) {
  46.         int key = a[i];
  47.         int k = i - 1;
  48.         for (; k >= 0; k--) {
  49.             if (a[k] > key) {
  50.                 a[k + 1] = a[k];
  51.             }
  52.             else {
  53.                 break;
  54.             }
  55.         }
  56.         a[k + 1] = key;
  57.     }
  58. }
  59.  
  60. void Merge(int a[], int left, int middle, int right) {
  61.     int i1 = left;
  62.     int i2 = middle + 1;
  63.     int n = right - left + 1;
  64.  
  65.     int* B = (int*)malloc(sizeof(int) * n);
  66.     int i = 0;
  67.  
  68.     while (i1 <= middle && i2 <= right) {
  69.         if (a[i1] <= a[i2]) {
  70.             B[i] = a[i1];
  71.             i1++;
  72.             i++;
  73.         }
  74.         else {
  75.             B[i] = a[i2];
  76.             i2++;
  77.             i++;
  78.         }
  79.     }
  80.  
  81.     while (i1 <= middle) {
  82.         B[i] = a[i1];
  83.         i1++;
  84.         i++;
  85.     }
  86.  
  87.     while (i2 <= right) {
  88.         B[i] = a[i2];
  89.         i2++;
  90.         i++;
  91.     }
  92.  
  93.     for (int j = 0; j < n; j++)
  94.         a[j + left] = B[j];
  95. }
  96.  
  97. void MergeSort(int a[], int left, int right) {
  98.     if (left == right)
  99.         return;
  100.     int middle = (left + right) / 2;
  101.     MergeSort(a, left, middle);
  102.     MergeSort(a, middle + 1, right);
  103.     Merge(a, left, middle, right);
  104. }
  105.  
  106. // 新的MergeSort3函数实现
  107. void MergeSort3(int a[], int left, int right) {
  108.     if (left < right) {
  109.         int middle1 = left + (right - left) / 3;
  110.         int middle2 = left + 2 * (right - left) / 3;
  111.  
  112.         MergeSort3(a, left, middle1);
  113.         MergeSort3(a, middle1 + 1, middle2);
  114.         MergeSort3(a, middle2 + 1, right);
  115.  
  116.         // 分配临时数组空间
  117.         int n = right - left + 1;
  118.         int* temp = (int*)malloc(sizeof(int) * n);
  119.  
  120.         int i = left, j = middle1 + 1, k = middle2 + 1, l = 0;
  121.  
  122.         while (i <= middle1 && j <= middle2 && k <= right) {
  123.             if (a[i] <= a[j] && a[i] <= a[k]) {
  124.                 temp[l++] = a[i++];
  125.             }
  126.             else if (a[j] <= a[i] && a[j] <= a[k]) {
  127.                 temp[l++] = a[j++];
  128.             }
  129.             else {
  130.                 temp[l++] = a[k++];
  131.             }
  132.         }
  133.  
  134.         while (i <= middle1 && j <= middle2) {
  135.             if (a[i] <= a[j]) {
  136.                 temp[l++] = a[i++];
  137.             }
  138.             else {
  139.                 temp[l++] = a[j++];
  140.             }
  141.         }
  142.  
  143.         while (i <= middle1 && k <= right) {
  144.             if (a[i] <= a[k]) {
  145.                 temp[l++] = a[i++];
  146.             }
  147.             else {
  148.                 temp[l++] = a[k++];
  149.             }
  150.         }
  151.  
  152.         while (j <= middle2 && k <= right) {
  153.             if (a[j] <= a[k]) {
  154.                 temp[l++] = a[j++];
  155.             }
  156.             else {
  157.                 temp[l++] = a[k++];
  158.             }
  159.         }
  160.  
  161.         while (i <= middle1) {
  162.             temp[l++] = a[i++];
  163.         }
  164.  
  165.         while (j <= middle2) {
  166.             temp[l++] = a[j++];
  167.         }
  168.  
  169.         while (k <= right) {
  170.             temp[l++] = a[k++];
  171.         }
  172.  
  173.         // 将排序好的元素复制回原数组
  174.         for (i = left, l = 0; i <= right; i++, l++) {
  175.             a[i] = temp[l];
  176.         }
  177.  
  178.         // 释放临时数组空间
  179.         free(temp);
  180.     }
  181. }
  182.  
  183. int main() {
  184.     char Sorting_Algorithm[] = "MergeSort3"; 
  185.  
  186.     int n = 20; 
  187.  
  188.     int* a = (int*)malloc(sizeof(int) * n);
  189.  
  190.     for (int i = 0; i < n; i++)
  191.         a[i] = rand() % n; 
  192.  
  193.     DisplayArray(a, n); 
  194.  
  195.     cout << "===========================================================\n";
  196.  
  197.     if (strcmp(Sorting_Algorithm, "BubbleSort") == 0) {
  198.         cout << "Test the bubble sort.\n";
  199.         BubbleSort(a, n);
  200.     }
  201.     else if (strcmp(Sorting_Algorithm, "InsertionSort") == 0) {
  202.         cout << "Test the insertion sort.\n";
  203.         InsertionSort(a, n);
  204.     }
  205.     else if (strcmp(Sorting_Algorithm, "MergeSort") == 0) {
  206.         cout << "Test the merge sort.\n";
  207.         int left = 0;
  208.         int right = n - 1;
  209.         MergeSort(a, left, right);
  210.     }
  211.     else if (strcmp(Sorting_Algorithm, "MergeSort3") == 0) {
  212.         cout << "Test the merge sort 3.\n";
  213.         int left = 0;
  214.         int right = n - 1;
  215.         MergeSort3(a, left, right);
  216.     }
  217.  
  218.     DisplayArray(a, n);
  219.  
  220.     cout << "===========================================================\n";
  221.  
  222.     free(a);
  223.  
  224.     return 0;
  225. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The elements in the array a[] are: 
3 6 17 15 13 15 6 12 9 1 2 7 10 19 3 6 0 6 12 16 
===========================================================
Test the merge sort 3.
The elements in the array a[] are: 
0 1 2 3 3 6 6 6 6 7 9 10 12 12 13 15 15 16 17 19 
===========================================================
https://ideone.com/xdBorl
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!