排序

1.冒泡排序

冒泡排序 bubble sort通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。
时间复杂度为O(n^2)

2.选择排序

选择排序 selection sort的工作原理非常直接：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。
时间复杂度为O(n^2)

3.插入排序

插入排序 insertion sort是一种简单的排序算法，工作原理:在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
归并排序¶

4.归并排序

归并排序 merge sort是一种基于分治策略的排序算法。
划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

5.快速排序

「快速排序 quick sort」是一种基于分治策略的排序算法，运行高效，应用广泛。
快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

6.堆排序

堆排序 heap sort是一种基于堆数据结构实现的高效排序算法。
输入数组并建立小顶堆，此时最小元素位于堆顶。
不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

7.桶排序

桶排序 bucket sort是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。
流程：
初始化k个桶，将n个元素分配到k个桶中。
对每个桶分别执行排序（本文采用编程语言的内置排序函数）。
按照桶的从小到大的顺序，合并结果。

代码

头文件算法实现

#ifndef SORT_H
#define SORT_H
#include <cstdio>
#include <iostream>
using namespace std;
template <class T> void shellSort(T *array, int n);               // shell排序
template <class T> void mergeSort(T *array, int left, int right); // 归并排序
template <class T>
void merge(T *arr, int left, int right,
           int middle); // 归并两个子序列，left middle right分成两个子序列
template <class T> void quickSort(T *array, int left, int right); // 快速排序
template <class T> void heapSort(T *array, int n);                // 堆排序
template <class T> void insertSort(T *array, int n); // 插入排序
template <class T> void bubbleSort(T *array, int n); // 冒泡排序
template <class T> void selectSort(T *array, int n); // 选择排序
template <class T> void swap(T *left, T *right);     // 交换左右两个值
template <class T> void showArray(const T *array, int n);       // 打印数组
template <class T> void HeapAdjust(T *arr, int start, int end); // 调整大堆
void RadixSort(int* array,int n);

// 1、选出一个key，一般是最左边或是最右边的。
// 2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
// 3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
// 4.此时key的左边都是小于key的数，key的右边都是大于key的数
// 5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
template <class T> void quickSort(T *array, int begin, int end) {
  if (begin > end)
    return;
  int tmp = *(array + begin);
  int i = begin;
  int j = end, t;
  while (i != j) {
    while (*(array + j) >= tmp && j > i)
      j--;
    while (*(array + i) <= tmp && j > i)
      ++i;
    if (j > i) {
      t = *(array + i);
      *(array + i) = *(array + j);
      *(array + j) = t;
    }
  }
  *(array + begin) = *(array + i);
  *(array + i) = tmp;
  quickSort(array, begin, i - 1);
  quickSort(array, i + 1, end);
}

template <class T> void shellSort(T *array, int n) {
  int gap = n, i, end, temp;
  while (gap > 1) {
    gap = gap / 3 + 1; // 调整希尔增量
    i = 0;
    for (i = 0; i < n - gap; ++i) // 从0遍历到n-gap-1
    {
      end = i;
      temp = *(array + end + gap);
      while (end >= 0) {
        if (*(array + end) > temp) {
          *(array + end + gap) = *(array + end);
          end -= gap;
        } else {
          break;
        }
      }
      *(array + end + gap) = temp; // 以 end+gap 作为插入位置
    }
  }
}
template <class T> void heapSort(T *arr, int n) {
  // 第一次建立大根堆，从后往前依次调整
  for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
    HeapAdjust(arr, i, n - 1);
  }
  // 每次将根和待排序的最后一次交换，然后在调整
  int tmp;
  for (int i = 0; i < n - 1; ++i) {
    tmp = *arr;
    *arr = *(arr + n - 1 - i);
    *(arr + n - 1 - i) = tmp;
    HeapAdjust(arr, 0, n - 1 - i - 1);
  }
}

template <class T> void HeapAdjust(T *arr, int start, int end) {
  int tmp = arr[start];
  for (int i = 2 * start + 1; i <= end; i = i * 2 + 1) {
    if (i < end && *(arr + i) < *(arr + i + 1)) // 有右孩子并且左孩子小于右孩子
    {
      ++i;
    } // i一定是左右孩子的最大值
    if (*(arr + i) > tmp) {
      *(arr + start) = *(arr + i);
      start = i;
    } else {
      break;
    }
  }
  *(arr + start) = tmp;
}

template <class T> void insertSort(T *array, int n) {
  int end, temp;
  for (int i = 0; i < n - 1; ++i) {
    // 记录有序序列最后一个元素的下标
    end = i;
    temp = *(array + end + 1);
    // 单趟排
    while (end >= 0) {
      // 比插入的数大就向后移
      if (temp < *(array + end)) {
        *(array + end + 1) = *(array + end);
        end--;
      }
      // 比插入的数小，跳出循环
      else
        break;
    }
    *(array + end + 1) = temp;
  }
}
template <class T> void bubbleSort(T *array, int n) {
  int i, j, a;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - i - 1; ++j) {
      if (*(array + j) > *(array + j + 1)) {
        a = *(array + j + 1);
        *(array + j + 1) = *(array + j);
        *(array + j) = a;
      }
    }
  }
}

template <class T>
void mergeSort(T *array, int left, int right) { // right为索引值，不是个数
  if (left >= right) {
    return;
  }
  int middle = (left + right) / 2;
  mergeSort(array, left, middle);
  mergeSort(array, middle + 1, right);
  merge(array, left, right, middle);
}
template <class T> void merge(T *arr, int left, int right, int middle) {
  int *aux;
  int i = left;       // i表示的是middle前面的数组的元素
  int j = middle + 1; // j表示的是middle之后的数组的元素
  int k = 0;          // k表示的是aux数组中的元素
  aux =
      (int *)malloc((right - left + 1) * sizeof(int)); // 为了开辟够足够的空间开存放数组各元素的内容
  for (k = left; k <= right; ++k) {
    *(aux + k - left) = *(arr + k); // 先将两个子数组中的元素全部输入进aux数组中
  }
  for (k = left; k <= right; ++k) {
    if (i > middle) {
      *(arr + k) = *(aux + j - left);
      ++j;
    } else if (j > right) {
      *(arr + k) = *(aux + i - left);
      ++i;
    } else if (*(aux + i - left) > *(aux + j - left)) {
      *(arr + k) = *(aux + j - left);
      ++j;
    } else {
      *(arr + k) = *(aux + i - left);
      ++i;
    }
  }
}

template <class T> void selectSort(T *array, int n) {
  int i, j, temp;
  for (i = 0; i < n - 1; ++i) {
    temp = i;
    for (j = i + 1; j < n; ++j) {
      temp = *(array + temp) > *(array + j) ? j : temp;
    }
    swap(array + i, array + temp);
  }
}
template <class T> void swap(T *left, T *right) {
  int a = *right;
  *right = *left;
  *left = a;
}
template <class T> void showArray(const T *array, int n) {
  int i = 0;
  while (i < n) {
    cout << *(array + i) << " ";
    ++i;
  }
  cout << endl;
}
#endif

测试代码

#include "sort.h"
#include <bits/types/clock_t.h>
#include <ctime>
template <class T> void createTestData(T *array, int size);
int main() {
  srand(time(nullptr)); // 设置随机数种子
  clock_t start,finish;
  int arr[] = {4, 2, 6, 1, 8, 3, 16, 10, 9, 2, 1, 11,2,1,4,3,-1,-1};

  cout << "shell排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  shellSort(arr, 16);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "堆排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  heapSort(arr, 16);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "选择排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  selectSort(arr, 16);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "冒泡排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  bubbleSort(arr, 16);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "插入排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  insertSort(arr, 16);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "快速排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  quickSort(arr, 0, 11);
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);

  createTestData(arr, 16);
  cout << "归并排序测试" << endl;
  cout << "排序前：";
  showArray(arr, 16);
  start=clock_t();
  mergeSort(arr, 0, 15); // left,right为下标，不是元素个数
  finish = clock();
  cout<<finish-start<<endl;
  cout << "排序后：";
  showArray(arr, 16);
}
template <class T> void createTestData(T *array, int size) {
  for (int i = 0; i < size; i++) {
    *(array + i) = rand() % 20;
  }
}

测试结果