一、排序算法
常见的内部排序算法有：选择排序、插入排序、冒泡排序、计数排序、归并排序、快速排序、堆排序、基数排序、希尔排序等。文本不介绍堆排序、基数排序、希尔排序。
二、算法性能比较
排序算法平均时间复杂度最小时间复杂度最大时间复杂度适用场景
选择排序O(N^2)O(N^2)O（N^2无脑排序，性能差插入排序O(N^2)O(N)O(N^2)某几个位置被打乱的冒泡排序O(N^2)O(N)O（N^2）基本有序计数排序O(Max(N,M))O(Max(N,M))O(Max(N,M)数据范围M较小归并排序O(N log N)O(N log N)O(N log N)所有快速排序O(N log N)O(N log N)O(N^2统计性能最好的算法
三、源码
#pragma once
class SortLib
{
private:
static void mergeSortInner(int* a, int *temp, int s, int e)
{
if (s == e)
{
return;
}
int m = (s + e) / 2;
mergeSortInner(a, temp, s, m);
mergeSortInner(a, temp, m + 1, e);
int i = s, j = s, k = m + 1;
while (i <= e)
{
if (a[j] <= a[k])
{
temp[i++] = a[j++];
if (j > m)
{
while (k <= e)
{
temp[i++] = a[k++];
}
}
}
else
{
temp[i++] = a[k++];
if (k > e)
{
while (j <= m)
{
temp[i++] = a[j++];
}
}
}
}
for (int i = s; i <= e; i++)
{
a[i] = temp[i];
}
}
static void quickSort(int* a, int s, int e)
{
if (s >= e)
{
return;
}
int m = (s + e) / 2;
int base = a[m];
a[m] = a[s];
a[s] = base;
int i = s + 1;
int j = e;
while (i <= j)
{
while (a[i] < base)
{
i++;
}
while (a[j] > base)
{
j--;
}
if (i < j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else //相等的元素放左边
{
i++;
}
}
a[s] = a[j];
a[j] = base;
quickSort(a, s, j - 1);
quickSort(a, j + 1, e);
}
public:
//选择排序
static void selectSort(int* a, int len)
{
for (int i = 0; i < len - 1; i++)
{
int m = a[i];
int mj = i;
for (int j = i + 1; j < len; j++)
{
if ( a[j] < m)
{
m = a[j];
mj = j;
}
}
a[mj] = a[i];
a[i] = m;
}
}
//冒泡排序
static void bubblingSort(int* a, int len) //保证前i最小
{
for (int i = 0; i < len - 1; i++)
{
bool swap = false;
for (int j = len - 1; j >i; j--)
{
if (a[j] < a[j - 1])
{
int t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
swap = true;
}
}
if(swap == false)
{
break;
}
}
}
//插入排序
static void insertSort(int* a, int len) //保证前i有序
{
for (int i = 1; i < len; i++)
{
int t = a[i];
int j;
for (j = i-1; j >=0 && a[j] > t; j--)
{
a[j+1] = a[j];
}
a[j+1] = t;
}
}
//计数排序
static void countSort(int* a, int len)
{
int min = a[0], max = a[0];
for (int i = 1; i < len; i++)
{
min = min < a[i] ? min : a[i];
max = max > a[i] ? max : a[i];
}
int* t = new int[max - min + 1];
for (int i = 0; i < max - min + 1; i++)
{
t[i] = 0;
}
for (int i = 0; i < len; i++)
{
t[a[i] - min]++;
}
for (int i = min, j = 0; i <= max; i++)
{
for (int k = 0; k < t[i - min]; k++)
{
a[j++] = i;
}
}
}
//归并排序
static void mergeSort(int* a, int len)
{
int* t = new int[len];
mergeSortInner(a, t, 0, len - 1);
delete t;
}
//快速排序
static void quickSort(int* a, int len)
{
quickSort(a, 0, len - 1);
}
};
