排序算法 - Sorting Algorithms

Posted on Edited on In , Views: Word count in article: 73 Reading time ≈ 1 mins.

排序算法合集

  • QuickSort
  • HeapSort
  • RadixSort
  • ShellSort

QuickSort

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void QuickSort(vector<int>& arr, size_t left, size_t right) {
  if (left - right >= 2) {
    int i = left;
    int j = right + 1;
    int tmp = arr[left];  // Using first element as pivot is not recommend
    while (i < j) {
      while (arr[--j] > tmp);
      while (arr[++i] < tmp);
      if (i < j)
        swap(arr[i], arr[j]);
      else
        break;
    }
    swap(arr[left], arr[j]);
    QuickSort(arr, left, j - 1, cnt + 1);
    QuickSort(arr, j + 1, right, cnt + 1);
  }
}

Time Complexity

  • Average:

  • Worst:

HeapSort

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void HeapSort(vector<int>& arr) {
  auto percDown = [](vector<int>& arr, size_t i, size_t n) {
    int tmp = arr[i];
    size_t j = i;
    size_t child;
    for (; 2 * j + 1 < n; j = child) {
      child = 2 * j + 1;
      if (child < n && child + 1 < n && arr[child + 1] > arr[child]) child++;
      if (tmp < arr[child])
        arr[j] = arr[child];
      else
        break;
    }
    arr[j] = tmp;
  };
  for (int i = arr.size() / 2 - 1; i >= 0; i--) {
    percDown(arr, i, arr.size());
  }

  for (int i = arr.size() - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    percDown(arr, 0, i);
  }
}

Time Complexity

  • Worst:

RadixSort

Implememt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void RadixSort(vector<int>& arr) {
  vector<vector<int>> buckets(10, vector<int>());
  size_t maxLen = 0;
  for (size_t i = 0; i < arr.size(); i++) {
    size_t len = 0;
    int tmp = arr[i];
    buckets[tmp % 10].push_back(arr[i]);
    do {
      len++;
    } while (tmp /= 10);
    maxLen = max(maxLen, len);
  }
  int idx = 0;
  for (size_t i = 0; i < 10; i++) {
    for (auto& it : buckets[i]) arr[idx++] = it;
    buckets[i].clear();
  }

  for (size_t t = 1; t < maxLen; t++) {
    for (size_t i = 0; i < arr.size(); i++) {
      int tmp = arr[i];
      for (size_t j = 0; j < t && tmp; j++) tmp /= 10;
      buckets[tmp % 10].push_back(arr[i]);
    }
    idx = 0;
    for (size_t i = 0; i < 10; i++) {
      for (auto& it : buckets[i]) arr[idx++] = it;
      buckets[i].clear();
    }
  }
}

Time Complexity

  • Worst:

where is max length of digits, and is the number of radix.

ShellSort

Implement

1
2
3
4
5
6
7
8
9
10
11
12
void ShellSort(vector<int>& arr) {
  size_t hs[] = {7, 3, 1};
  for (size_t t = 0; t < 3; t++) {
    size_t h = hs[t];
    for (size_t i = h; i < arr.size(); i++) {
      int tmp = arr[i];
      size_t j = i;
      for (; j >= h && arr[j - h] > tmp; j -= h) arr[j] = arr[j - h];
      arr[j] = tmp;
    }
  }
}

Time Complexity

  • Worst: