資料結構筆記（1）：基礎排序

這裡介紹三個O(n^2)的排序算法即插入排序、選擇排序和冒泡排序，這三個排序算法應該是所有排序中最簡單的。

插入排序：在已經排好序的序列中找一個合适的位置，将那個未被排序的數插入那個位置即可。

選擇排序：在未排序序列找到一個最小值放到已排序的序列後面即可。

冒泡排序：每循環一次，通過逐位交換的方式将最大值往未排序的序列的最後一位推即可。

下面的代碼針對不同的測試資料對上面三種算法的時間性能進行了相應測試

1.首先我們實作一個用于測試排序算法時間效率的類

#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H

#include <bits/stdc++.h>

using namespace std;

namespace SortTestHelper {
  int* generateRandomArray(int n, int rangeL, int rangeR) { 
    // 生成長度為n 且數值範圍在rangeL 到 rangeR 之間的随機數組
    int* arr = new int[n];
    srand(time(0));
    for (int i = 0; i < n; i++) {
      arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
    }
    return arr;
  }

  int* generateNearlyOrderedArray(int n, int swapTimes) { // 生成長度為n，且幾乎有序的數組
    int* arr = new int[n];
    iota(arr, arr + n, 1); // 按順序生成1--n
    srand(time(0));
    while (swapTimes--) {
      int posx = rand() % n;
      int posy = rand() % n;
      swap(arr[posx], arr[posy]);
    }
    return arr;
  }

  int* copyIntArray(int a[], int n) {
    int* arr = new int[n];
    copy(a, a + n, arr);
    return arr;
  }

  bool isSorted(int n, int arr[]) {
    for (int i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        return false;
      }
    }
    return true;
  }

  void testSort(string sortName, void(*sort)(int[], int), int arr[], int n) { // 計算算法的執行的時間
    clock_t startTime = clock();
    sort(arr, n);
    clock_t endTime = clock();
    assert(isSorted(n, arr));
    cout << sortName << ":";
    printf("%.7f s\n", double(endTime - startTime) / CLOCKS_PER_SEC);
  }


}

#endif // SORTTESTHELPER_H
           

2.我們再實作上面提到的3個算法。

void insertionSort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int tmp = arr[i];
    int j;
    for (j = i - 1; j >= 0; j--) {
      if (tmp < arr[j]) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = tmp;
  }
}

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr[minIndex], arr[i]);
  }
}

void bubbleionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    bool flag = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true;
        swap(arr[j], arr[j + 1]);
      }
    }
    if (!flag) {
      break;
    }
  }
}

void test0() { // 對随機的n個數進行測試
  int n = 10000;
  int* arr1 = SortTestHelper::generateRandomArray(n, 1, n);
  int* arr2 = SortTestHelper::copyIntArray(arr1, n);
  int* arr3 = SortTestHelper::copyIntArray(arr1, n);
  SortTestHelper::testSort("insertionSort", insertionSort, arr2, n);
  SortTestHelper::testSort("selectionSort", selectionSort, arr1, n);
  SortTestHelper::testSort("bubbleionSort", bubbleionSort, arr3, n);
  delete[] arr1;
  delete[] arr2;
  delete[] arr3;
}

void test1() { // 對幾乎有序的n個數進行測試
  int n = 100000;
  int* arr1 = SortTestHelper::generateNearlyOrderedArray(n, 100);
  int* arr2 = SortTestHelper::copyIntArray(arr1, n);
  int* arr3 = SortTestHelper::copyIntArray(arr1, n);

  SortTestHelper::testSort("insertionSort", insertionSort, arr1, n);
  SortTestHelper::testSort("selectionSort", selectionSort, arr2, n);
  SortTestHelper::testSort("bubbleionSort", bubbleionSort, arr3, n);

  delete[] arr1;
  delete[] arr2;
  delete[] arr3;
}
           

當n=10000時且為随機數的情況：

我們可以看出插入排序是最快的

當n=10000時且近乎有序的情況：

還是插入排序最快，且選擇排序的時間幾乎沒變，說明選擇排序幾乎不受原有資料的順序性的影響

當n=100000時且為随機數的情況：

插入排序還是最快的，且三個排序的時間大于為n=10000時所消耗時間的100倍，是以資料量和時間是一個平方的關系

當n=100000時且近乎有序的情況：

可以看出選擇排序的時間和n=100000時且為随機數幾乎一樣，這跟進一步說明了選擇排序不受原有資料順序性的影響，而冒泡卻快了很多這是因為我們的代碼中進行了一步優化。