常用排序方法(冒泡，快速排序，堆排序)

算法动图来自菜鸟教程（侵删）
参考链接：十大经典排序算法

冒泡排序

算法原理

以从小到大为例，从头开始遍历数组，只要遇到前面比后面小的，就交换两者位置，直到末尾，最多循环n-1次。

算法步骤

• 比较相邻的元素，如果第一个比第二个大，就交换两个元素位置。
• 对每一对元素执行该操作，从开始一对到结尾最后一对，这个步骤做完，最后的元素应该是最大的元素。
• 针对除开最后一个元素的剩下元素。
  

测试代码

#include 
using namespace std;
class Solution {
 public:
  void Bubblesort(int *input, int size) {
    for (int i = 0; i < size - 1; i++) {
      for (int j = 0; j < size - i - 1; j++) {
        if (input[j] < input[j + 1]) {
          int temp = 0;
          temp = input[j];
          *(input + j) = input[j + 1];
          *(input + j + 1) = temp;
        }
      }
    }
  }
  void CreateNum(int *nums) {
    for (int i = 0; i < 10; i++) {
      *(nums + i) = i;
    }
  }
  void PrintNum(int *nums) {
    for (int i = 0; i < 10; i++) {
      cout << *(nums + i) << " :";
    }
    cout << endl;
  }
};
int main() {
  int nums[10];
  int *p = nums;
  Solution a;
  a.CreateNum(p);
  a.PrintNum(p);
  a.Bubblesort(p, 10);
  a.PrintNum(p);
  return 0;
}
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
32
33
34
35
36
37
38

执行结果

快速排序

算法原理

分而治之，将一段数据根据基准数（比它大，比它小于等于)划分为两部分。

对划分后的两个数组递归执行划分。

算法步骤

• 选定一个基准数（一般是最左边），根据比其小或者比它大将数组划分为两个数组。
• 将划分后的数组递归执行划分。

测试代码

#include 
using namespace std;
class Solution {
 public:
  int Paritition(int arr[], int left, int right) {
    int pivot = arr[left];
    while (left < right) {
      while (left < right && arr[right] >= pivot) {
        right--;
      }
      arr[left] = arr[right];
      while (left < right && arr[left] <= pivot) {
        left++;
      }
      arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
  }
  void QuickSort(int input[], int start, int end) {
    if (start < end) {
      int pivot = Paritition(input, start, end);
      QuickSort(input, start, pivot - 1);
      QuickSort(input, pivot + 1, end);
    }
  }
  void CreateNum(int *nums) {
    for (int i = 0, j = 10; i < 10; i++, j--) {
      *(nums + i) = j;
    }
  }
  void PrintNum(int *nums) {
    for (int i = 0; i < 10; i++) {
      cout << *(nums + i) << " :";
    }
    cout << endl;
  }
};
int main() {
  int nums[10];
  int *p = nums;
  Solution a;
  a.CreateNum(p);
  a.PrintNum(p);
  a.QuickSort(nums, 0, 9);
  a.PrintNum(p);
  return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

运行截图：

堆排序

算法原理

算法步骤

代码实测