选择排序，冒泡排序，快速排序，归并排序，插入排序，希尔排序，计数排序，桶排序，基数排序

以上是一些常用的排序算法。

选择排序

for(int i = 0; i < n; i++) {

int minval = a[i];

int minid = i;

for (int j = i+1; j < n; j++) {

if (a[j] < minval) {

minid = j;

minval = a[j];

}

}

swap(a[i], a[minid]);

}

最简单的就是选择排序，就是每次遍历数组，然后依次得到第一小的，第二小的，知道整个数组递增有序。所以时间复杂度也很好理解就是O(n^2),

冒泡排序

冒泡排序时学编程开始学到的第一个排序，刚开始还觉得很难理解，哈哈~

用两种思路，每次从后往前，大的下沉；或者从前往后小的上浮；

大的下沉，最次的最大会在右边：

/u012864854/article/details/79404463

include <bits/stdc++.h>

using namespace std;

int n;

int a[10] = {9, 19, 7, 2, 4, 5, 6, 8, 10, 11};

void showArray() {

for (int i = 0; i < n; i++) {

cout << a[i] << " ";

}

cout << endl;

}

int main() {

// cin >> n;

n = 10;

for (int i = 0; i < n-1; i++) {//最多进行n-1趟

for (int j = 0; j < n-1-i; j++) {

if (a[j] > a[j + 1]) swap(a[j], a[j+1]);

}

}

showArray();

return 0;

}

或者小的上浮：

include <bits/stdc++.h>

using namespace std;

int n;

int a[10] = {9, 19, 7, 2, 4, 5, 6, 8, 10, 11};

void showArray() {

for (int i = 0; i < n; i++) {

cout << a[i] << " ";

}

cout << endl;

}

int main() {

// cin >> n;

n = 10;

for (int i = 0; i < n-1; i++) {//最多进行n-1趟

for (int j = n-1; j > i; j--) {

if (a[j] < a[j - 1]) swap(a[j], a[j - 1]);

}

}

showArray();

return 0;

}

由此可见时间复杂度O(N^2),但是最好的情况下(递增序列)，O(N*lgN)

快速排序

一般情况下时间复杂度是O(N*lgN),但是不稳定，最坏也是O(N^2);

快排采用分治，递归的思想，进行排序；

总体的思路就是首先定义l = 0, r = len-1,两个端点，

每次选择当前数组第一个数作为基点，然后在满足l <=r的情况下，不断交换右边和左边的数；然后递归进行；

void quickSort(int a[], int left, int right) {

if (left > right) return;

int base = a[left];

int i = left, j = right;while (i < j) {while (i < j && a[j] >= base) j--;while (i < j && a[i] <= base) i++;swap(a[i], a[j]);}a[left] = a[i];a[i] = base;quickSort(a, left, i-1);quickSort(a, i+1, right);

}

归并排序

所谓的归并排序，就是每次把两个两个的子序列合并排序，直到整个序列有序，刚开始的子序列长度是1，然后不断*2递增；

时间复杂度O(N*lgN),比较稳定,最好也是O(N)

void mergeSort() {

for (int step = 2; step/2 <= n; step *= 2) {

for (int i = 0; i < n; i += step) {

sort(tempOri + i, tempOri + min(i + step, n));

}

}

}

或者采用分治递归；

void mergearray(int arr[], int from, int mid, int to, int temp[]) {

int i = from;

int inter = mid + 1;

int k = 0;

while (from <= mid && inter <= to) {

if (arr[from] < arr[inter])

temp[k++] = arr[from++];

else

temp[k++] = arr[inter++];

}

while (from <= mid)

temp[k++] = arr[from++];

while (inter <= to)

temp[k++] = arr[inter++];

for (int j = 0; j < k; j++) {arr[j + i] = temp[j];}

}

void mergeSort(int arr[], int from, int to, int temp[]) {

if (from < to) {

int mid = (from + to) / 2;

mergeSort(arr, from, mid, temp);

mergeSort(arr, mid + 1, to, temp);

mergearray(arr, from, mid, to, temp);

}

}

插入排序

每次像已经排好序的序列里插入一个新的数，然后对当前进行排序，所以过程中的每次得到的一个小的序列都是递增有序的；

比较稳定，一般复杂度O(N*lgN),最好O(N)

void insertSort() {

for (int i = 1; i < n; i++) {

int temp = tempOri[i], j = i;

while (j > 0 && tempOri[j - 1] > temp) {

tempOri[j] = tempOri[j - 1];

j--;

}

tempOri[j] = temp;

}

}

希尔排序

希尔排序时插入的排序的升级版，有一个递减的增量序列，一般都是按数组大小n,不断按n/2的增量div，每次比较相隔增量之间这几个数，对这几个数进行排序；

时间复杂度不确定，不稳定，最好就是O(N)。

void shellSort() {

int len = n;

for (int div = len/2; div >= 1; div = div/2) {

//对于每一个增量

for (int i = 0; i <= div; i++) {

for (int j = i; j < len - div; j += div) {

for (int k = j; k < len; k += div) {

if (tempOri[j] > tempOri[k]) {

swap(tempOri[j], tempOri[k]);

}

}

}

}

}

}

堆排序

堆排序并不是很稳定，然后时间复杂度一般是O(N*lgN);

对于一个大顶堆，堆顶的元素是最大的，所以把它和最后一个元素交换后，最后一个元素就是最大的，然后在对前面的除了已经确定大小顺序的（后面的）进行堆调整。循环如此的操作，依次在倒数第二个得到第二大的数，如此就可以得到递增序列。

因此要求递增的序列，用堆排序需要 用大顶堆，递减的序列，用堆排序需要用小顶堆。

首先是建堆，从最后一个非叶子结点开始往前依次建堆，调整，保证每个结点都是以其为根结点的子树中权值最大的结点。证见算法导论。

//调整大顶堆，在已经建立好的基础下；

void downAjust(int low, int high) {

int i = low, j = i2;//j为左孩子结点

while (j <= high) {//存在孩子结点

//如果存在右孩子，并且右孩子结点的值大于左孩子结点的值

if (j + 1 <= high && heap[j + 1] > heap[j]) {

j++;

}

if (j <= high && heap[j] > heap[i]) {

swap(heap[j], heap[i]);

i = j;

}

else {

break;

}

j = i2;

}

}

void createHeap() {

for (int i = n/2; i >= 1; i--) {

downAjust(i, n);//建堆

}

}

void heapSort() {

//因为最后要求升序，所以先建大顶堆；先从非叶子结点开始

createHeap();

for (int i = n; i > 1; i--) {

swap(tempOri[i], tempOri[1]);//与堆顶交换

downAjust(1, i-1);//调整堆顶

}

}

计数排序

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

比如我们有三个数组a, b, c;

a是原始数组，待排序数组，数组里元素乱序；

然后c数组作为辅助数组，c[a[i]]记录的是当前之前有多少个元素比a[i]小，这样就可以用c数组来得出最后排序数组b中元素的位置，这样b[c[a[i]]] 就是a[i]在最后排序好之后的位置。以上就是基本的思想。

计数排序比较稳定，时间复杂度大约为O(n+k);

借用辅助数组c,得出排序后的序列b

代码如下:

include <bits/stdc++.h>

using namespace std;

const int maxn = 10000;

int a[maxn], b[maxn], c[maxn];

int n;

int main() {

cin >> n;

for (int i = 0; i < n; i++) {

cin >> a[i];

c[a[i]]++;

}

for (int i = 1; i < k; i++) {

c[i] += c[i - 1];

}

for (int i = n-1; i >= 0; i--) {

b[--c[a[i]]] = a[i];

}

for (int i = 0; i < n; i++) {

cout << b[i] << " ";

}

cout << endl;

return 0;

}

此外还可以对计数排序进行空间上的优化：

算法的步骤如下：

1.找出待排序的数组中最大和最小的元素

2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1

include <bits/stdc++.h>

using namespace std;

const int maxn = 10000;

const int INF = 0x3f3f3f3f;

int a[maxn], b[maxn], c[maxn];

int n;

int main() {

cin >> n;

int MIN = INF, MAX = -1;

for (int i = 0; i < n; i++) {cin >> a[i];if (a[i] < MIN) { MIN = a[i]; }if (a[i] > MAX) { MAX = a[i]; }}for (int i = 0; i < n; i++) {c[a[i]-MIN]++;}//int k = MAX-MIN+1;k为C数组的大小int k = MAX-MIN+1for (int i = 1; i < k; i++) {c[i] += c[i - 1];}for (int i = n-1; i >= 0; i--) {b[--c[a[i]-MIN]] = a[i];}for (int i = 0; i < n; i++) {cout << b[i] << " ";}cout << endl;return 0;

}

桶排序

桶排序很好理解，比如有一个序列a{3, 2, 9, 7, 5}

那么有我们有标号为0-10的桶c，然后遍历a,记录的是c[a[i]]++;

然后按标号从小到大输出，如果桶中元素不止一个，那么就输出多次；

include <bits/stdc++.h>

using namespace std;

const int maxn = 10000;

const int INF = 0x3f3f3f3f;

int a[maxn], b[maxn], c[maxn];

int n;

int main() {

cin >> n;

int MAX = -1;

for (int i = 0; i < n; i++) {

cin >> a[i];

MAX = max(MAX, a[i]);

}

cout << MAX << endl;

int C = MAX + 1;

int c[C];memset(c, 0, sizeof(c));for (int i = 0; i < n; i++) {c[a[i]]++;}for (int i = 0; i < C; i++) {if (c[i] > 0) {for (int j = 0; j < c[i]; j++) {cout << i << " ";}}}return 0;

}

基数排序

时间复杂度为O (nlog(r)m)，简称O(N*K)

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。--百度百科

有两种实现方法

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

时间效率[1]：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

include <bits/stdc++.h>

using namespace std;

const int maxn = 10000;

const int INF = 0x3f3f3f3f;

int a[maxn], b[maxn], c[maxn];

int n;

//求数据的最大位数

int maxbit(int data[], int n) {

int d = 1;

int p = 10;

for (int i = 0; i < n; i++) {

while (data[i] >= p) {

p *= 10;

++d;

}

}

return d;

}

void print(int a[], int n) {

for (int i = 0; i < n; i++) {

cout << a[i] << " ";

}

cout << endl;

}

void radixSort(int a[], int n) {

int d = maxbit(a, n);

int tmp[n];

fill(tmp, tmp+n, 0);

int radix = 1;

//进行d次排序

for (int i = 1; i <= d; i++) {

//每次分配前清空计数器

fill(c, c+10, 0);//注意这里只开了10

for (int j = 0; j < n; j++) {int k = (a[j]/radix)%10;//统计桶c[k]++;}for (int j = 1; j < 10; j++) {c[j] += c[j - 1];}for (int j = n-1; j >= 0; j--) {int k = (a[j]/radix)%10;tmp[--c[k]] = a[j];}//收集数据到a数组for (int j = 0; j < n; j++) {a[j] = tmp[j];}radix *= 10;}print(a, n);

}

int main() {

int n;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> a[i];

}

radixSort(a, n);

return 0;

}

/**

9

5 9 3 12 7 6 4 2 0

**/