【C/C++】几大排序算法：选择排序、插入排序、冒泡排序、归并排序、快速排序

#include <iostream>
using namespace std;
void swap(int* a, int* b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void selectSort(int ret[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int min = i;
    for (int j = i + 1; j < n; j++) {
      if (ret[j] < ret[min]) {
        swap(ret[j], ret[min]);
      }
    }
  }
}
void bubbleSort(int ret[], int n) {
  int count = 0;
  for (int i = 0; i < n - 1; i++) {
    bool sorted = true;
    count++; //该程序执行的次数
    for (int j = 0; j < n - i - 1; j++) {
      if (ret[j + 1] < ret[j]) {
        swap(ret[j + 1], ret[j]);
        sorted = false;//当程序已经排好序后立马跳出循环，                      
      }                //减少不必要的循环以提高效率
    }
    if (sorted) break;
  }
  cout << "该冒泡排序算法一共执行了" << count << "次!" << endl;


  for (int i = 0; i < n - 1; i++) {
    bool sorted = true;
    /*for (int j = 0; j < n - i - 1; j++) { //从左到右排序
      if (ret[j] > ret[j + 1]) {
        swap(ret[j], ret[j + 1]);
        sorted = false;
      }
    }*/
    for (int j = n - 1; j > i; j--) { //从右到左排序
      if (ret[j - 1] > ret[j]) {
        swap(ret[j - 1], ret[j]);
        sorted = false;//当程序已经排好序后立马跳出循环，                      
      }                //减少不必要的循环以提高效率}
    }
  }
}
void insertSort(int ret[], int n) {
  for (int i = 0; i < n; i++) {
    int current = ret[i];
    int preIndex = i - 1;
    while (preIndex >= 0 && ret[preIndex] > current) {
      ret[preIndex + 1] = ret[preIndex];
      preIndex--;
    }
    ret[preIndex + 1] = current;
  }
}
void mergeAdd(int ret[], int left, int mid, int right, int* tmp) {
  int i = left;
  int j = mid;
  int k = left;
  while (i < mid && j <= right) {
    if (ret[i] < ret[j]) {
      tmp[k++] = ret[i++];
    }
    else {
      tmp[k++] = ret[j++];
    }
  }
  while (i < mid) {
    tmp[k++] = ret[i++];
  }
  while (j <= right) {
    tmp[k++] = ret[j++];
  }
  memcpy(ret + left, tmp + left, sizeof(int) * (right - left + 1));
}
void mergeSort(int ret[], int left, int right, int* tmp) {//归并排序,递归思想
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(ret, left, mid, tmp);
    mergeSort(ret, mid + 1, right, tmp);
    mergeAdd(ret, left, mid + 1, right, tmp);
  }
}
int parttion(int ret[], int low, int high) {
  int i = low;
  int j = high;
  int base = ret[low];//从左到右选大的，从右到左选小的
  //if (low < high) {
  while (i < j) {
    while (i < j && ret[j] >= base) {
      j--;
    }
    if (i < j) { //程序走到这里说明已经找到小于base的ret[j]了
      ret[i++] = ret[j];
    }
    while (i < j && ret[i] < base) {
      i++;
    }
    if (i < j) { //程序走到这里说明已经找到大于base的ret[i]了
      ret[j--] = ret[i];
    }
  }
//}
  ret[i] = base;
  return i;//返回中间的坐标
}
void quickSort(int* ret, int low, int high) {
  if (low < high) {
    int mid = parttion(ret, low, high);
    quickSort(ret, low, mid - 1);
    quickSort(ret, mid + 1, high);
  }
}
void display(int ret[], int n) {
  cout << "排序后的结果：\n";
  for (int i = 0; i < n; i++) {
    cout << ret[i] << " ";
  }
  cout << endl;
}
int main() {
  int ret[] = { 161,163,159,170,157,172,165,160,112 };
  int len = sizeof(ret) / sizeof(ret[0]);
  int* tmp = new int[len];
  //selectSort(ret, len);//选择排序
  //bubbleSort(ret, len);//冒泡排序
  //insertSort(ret, len);//插入排序
  //mergeSort(ret, 0, len - 1, tmp);//归并排序
  quickSort(ret, 0, len - 1);//快速排序
  display(ret, len);

  return 0;
}