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.     free(B);
  97. }
  98.  
  99. void MergeSort(int a[], int left, int right) {
  100.     if (left == right)
  101.         return;
  102.     int middle = (left + right) / 2;
  103.     MergeSort(a, left, middle);
  104.     MergeSort(a, middle + 1, right);
  105.     Merge(a, left, middle, right);
  106. }
  107.  
  108. // 实现MergeSort3函数
  109. void MergeSort3(int a[], int left, int right) {
  110.     if (left < right) {
  111.         int middle1 = left + (right - left) / 3;
  112.         int middle2 = left + 2 * (right - left) / 3;
  113.  
  114.         MergeSort3(a, left, middle1);
  115.         MergeSort3(a, middle1 + 1, middle2);
  116.         MergeSort3(a, middle2 + 1, right);
  117.  
  118.         int n = right - left + 1;
  119.         int* temp = (int*)malloc(sizeof(int) * n);
  120.  
  121.         int i = left, j = middle1 + 1, k = middle2 + 1, l = 0;
  122.  
  123.         while (i <= middle1 && j <= middle2 && k <= right) {
  124.             if (a[i] <= a[j] && a[i] <= a[k]) {
  125.                 temp[l++] = a[i++];
  126.             }
  127.             else if (a[j] <= a[i] && a[j] <= a[k]) {
  128.                 temp[l++] = a[j++];
  129.             }
  130.             else {
  131.                 temp[l++] = a[k++];
  132.             }
  133.         }
  134.  
  135.         while (i <= middle1 && j <= middle2) {
  136.             if (a[i] <= a[j]) {
  137.                 temp[l++] = a[i++];
  138.             }
  139.             else {
  140.                 temp[l++] = a[j++];
  141.             }
  142.         }
  143.  
  144.         while (i <= middle1 && k <= right) {
  145.             if (a[i] <= a[k]) {
  146.                 temp[l++] = a[i++];
  147.             }
  148.             else {
  149.                 temp[l++] = a[k++];
  150.             }
  151.         }
  152.  
  153.         while (j <= middle2 && k <= right) {
  154.             if (a[j] <= a[k]) {
  155.                 temp[l++] = a[j++];
  156.             }
  157.             else {
  158.                 temp[l++] = a[k++];
  159.             }
  160.         }
  161.  
  162.         while (i <= middle1) {
  163.             temp[l++] = a[i++];
  164.         }
  165.  
  166.         while (j <= middle2) {
  167.             temp[l++] = a[j++];
  168.         }
  169.  
  170.         while (k <= right) {
  171.             temp[l++] = a[k++];
  172.         }
  173.  
  174.         for (i = left, l = 0; i <= right; i++, l++) {
  175.             a[i] = temp[l];
  176.         }
  177.  
  178.         free(temp);
  179.     }
  180. }
  181.  
  182. int main() {
  183.     char Sorting_Algorithm[] = "MergeSort3"; 
  184.  
  185.     int n = 20; 
  186.  
  187.     int* a = (int*)malloc(sizeof(int) * n);
  188.  
  189.     for (int i = 0; i < n; i++)
  190.         a[i] = rand() % n; 
  191.  
  192.     DisplayArray(a, n); 
  193.  
  194.     cout << "===========================================================\n";
  195.  
  196.     if (strcmp(Sorting_Algorithm, "BubbleSort") == 0) {
  197.         cout << "Test the bubble sort.\n";
  198.         BubbleSort(a, n);
  199.     }
  200.     else if (strcmp(Sorting_Algorithm, "InsertionSort") == 0) {
  201.         cout << "Test the insertion sort.\n";
  202.         InsertionSort(a, n);
  203.     }
  204.     else if (strcmp(Sorting_Algorithm, "MergeSort") == 0) {
  205.         cout << "Test the merge sort.\n";
  206.         int left = 0;
  207.         int right = n - 1;
  208.         MergeSort(a, left, right);
  209.     }
  210.     else if (strcmp(Sorting_Algorithm, "MergeSort3") == 0) {
  211.         cout << "Test the merge sort 3.\n";
  212.         int left = 0;
  213.         int right = n - 1;
  214.         MergeSort3(a, left, right);
  215.     }
  216.  
  217.     DisplayArray(a, n);
  218.  
  219.     cout << "===========================================================\n";
  220.  
  221.     free(a);
  222.  
  223.     return 0;
  224. }
Success #stdin #stdout 0s 5276KB
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/3thCLc
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!