1、排序的分类：

1.1内排序：

排序的整个过程中，待排序的所有记录全部放在内存中(本文主要介绍内排序的多种方法)

1.2外排序：

由于排序的记录个数太多，不能同时放在内存，整个排序需要在内外存之间交换数据才能进行

2、八大排序：

八大排序的时间复杂度，空间复杂度以及稳定性整理如下：

冒泡排序:时间复杂度O(n^2),空间复杂度O（1）,稳定

归并排序,时间复杂度O(nlogn);空间复杂度O(nlogn),稳定

快速排序，时间复杂度O(nlogn),空间复杂度O(logn) 不稳定

桶排序 时间复杂度O(n),空间复杂度O(n),稳定

简单选择排序 时间复杂度 O（n^2） 空间复杂度O（1）不稳定

直接插入排序，时间复杂度O（n^2） 空间复杂度O（1） 稳定的

希尔排序 时间复杂度O(n^1.3~1.5) 空间复杂度O(1) 不稳定

堆排序 时间复杂度O(nlogn) 空间复杂度O(1) 不稳定

2.1冒泡排序

2.1.1冒泡排序的规则：

两两关键字，如果反序则交换，直到没有反序的记录为止。

2.1.2代码：

void Bubble_Sort(int arr[], int n)//传入待排序数组，数组元素

{

bool tag = true;

for (int i = 0; i < n-1; i++)//冒泡排序一共进行多少轮(少一轮)，

{

tag = true;

for (int j = 0; j <n-1-i; j++)//每一轮交换的次数

{

if (arr[j] > arr[j+1])

{

tag = false;

Swap(arr[j], arr[j + 1]);

}

}

if (tag)

{

break;

}

}

}

2.1.3冒泡排序的优化：

void Bubble_Sort(int arr[], int n)

{

bool flag = true;

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

{

flag = true;

//从上往下进行

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

{

if (arr[j] < arr[j + 1])

{

flag = false;

swap(arr[j], arr[j + 1]);

}

}

if (flag)

{

break;

}

flag = false;

//从下往上进行

for (int k = n – i – 2; k > i; k–)

{

if (arr[k] < arr[ k – 1])

{

flag = false;

swap(arr[k], arr[k – 1]);

}

}

if (flag)

{

break;

}

}

}

2.2简单选择排序

2.2.1简单选择排序的规则：

简单选择排序法就是通过n-i次关键字之间的比较，从n-i-1个记录中选出关键字最小的记录，并和第i个记录交换值。

2.2.2代码：

void Select_Sort(int arr[], int n)

{

int min = 0;

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

{

min = i;

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

{

if (arr[min] > arr[j])

{

min = j;

}

}

if (min != i)

{

Swap(arr[i], arr[min]);

}

}

}

2.3直接插入排序

2.3.1直接插入排序的规则：

2.3.1代码：

void Insert_Sort(int arr[], int n)

{

int j = 0;

int tmp = 0;

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

{

tmp = arr[i];

for (j = i – 1; j >= 0; j–)

{

if (arr[j] > tmp)

{

arr[j + 1] = arr[j];

}

else

{

break;

}

}

arr[j+1] = tmp;

}

}

2.4希尔排序

2.4.1希尔排序的规则

先分组，然后进行直接插入排序：

2.4.2代码：

void Shell(int arr[], int n,int gap)

{

int tmp = 0;

int j = 0;

for (int i = gap; i < n; i+gap)

{

tmp = arr[i];

for (j = i – gap; j >= 0; j = j – gap)

{

if (arr[j] > tmp)

{

arr[j + gap] = arr[j];

}

}

arr[j + gap] = tmp;

}

}

void Shell_Sort(int arr[], int n)

{

int gap[3] = { 5,3,1 };

int len = sizeof(gap) / sizeof(gap[0]);

for (int i = 0; i < len; i++)

{

Shell(arr, n, gap[i]);

}

}

2.5堆排序

2.5.1堆排序的基本概念：

1）要进行堆排序，首先需要知到下面两个概念：

大顶锥：每一个结点的值都大于或等于它的左右子节点的值（如果我们调整之后根节点是最大值，将其放到最后，实现从小到大进行排序）

小顶锥：每一个结点的值都小与或等于它的左右子节点的值（如果我们调整之后根节点是最小值，将其放到最后，实现从大到小进行排序）

2）堆排序：

①将数组排序成为一个大顶锥

②将根节点（最大的值）和堆的末尾元素进行交换，从而使得末尾元素就是最大值

③将剩余n-1个元素重新构造成一个堆

如此反复执行就能得到一个有序数列了。

2.5.2代码：

void Heap_AD_Sort(int arr[],int begin, int end)

{

int tmp=arr[begin];//先定义一个变量存放根节点的数值

for (int i = begin*2+1; i <= end; i = begin * 2 + 1)

{

if (arr[i + 1] > arr[i] && i < end)//表示有右节点并且左节点的值比右节点的值小

{

i++;//调整到右节点上，使得保证i所在的小标是子节点中最大的

}

if (arr[i] > tmp)//此时子节点的值比根节点还要大一些

{

arr[begin] = arr[i];

begin = i;

}

else//否则根节点的值最大，不用交换，退出循环

{

break;

}

}

}

void Heap_Sort(int arr[], int n)

{

//从后向前先调整为大顶锥,从最后一个非叶子节点开始调整【最后一个非叶子结点的下标=（最后一个结点的下标-1）/2】

for (int i = (n – 1 – 1) / 2; i >= 0; i–)

{

Heap_AD_Sort(arr, i, n – 1);

}

for (int i = 0; i < n – 1; i++)//O(n)

{

Swap(arr[i], arr[n – i – 1]);//将根节点和最后一个叶子节点进行交换,

Heap_AD_Sort(arr, 0, (n – i – 1) – 1);//O(logn)，再次调整为大顶锥

}

}

2.6归并排序

2.6.1归并排序的基本思想：

最开始将数组单个为一组，则每组局部有序，再两两合并，直到能把所有数据放到同一组内，则完成。

2.6.2代码：

void Merge(int arr[], int n, int gap)

{

int *nums= (int*)malloc(sizeof(int) * n);

assert(nums != nullptr);

int i = 0;

int low1 = 0;

int high1 = low1 + gap – 1;

int low2 = high1 + 1;

int high2 = low2 + gap – 1 > n ? n – 1 : low2 + gap – 1;

while (low2 < n)//两组都存在

{

while (low1 <= high1 && low2 <= high2)

{

if (arr[low1] <= arr[low2])

{

nums[i++] = arr[low1];

}

else

{

nums[i++] = arr[low2];

}

}

while (low1 <= high1)

{

nums[i++] = arr[low1++];

}

while (low2 <= high2)

{

nums[i++] = arr[low2++];

}

low1 = high2 + 1;

high1 = low1 + gap – 1;

low2 = high1 + 1;

high2 = low2 + gap – 1 > n ? n-1 : low2 + gap – 1;

}

while (low1 < n)

{

nums[i++] = arr[low1++];

}

for (int j = 0; j < n; j++)

{

arr[j] = nums[j];

}

free(nums);

nums = nullptr;

}

void Merge_Sort(int arr[], int n)

{

for (int i = 1; i < n; i *= 2)

{

Merge(arr, n, i);

}

}

2.7快速排序

2.7.1快速排序的基本思想：

通过一趟排序将代拍记录分割成独立的两部分，其中在哪个一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序的目的。

2.7.2从小到大进行快速排序的规则：

以第一个数字为基准值

先从右边开始，

如果右边元素比基准值小，就和左边值交换，然后左边下标往后移

如果右边元素比基准值大，右边下标继续往前移动，之后遇到比基准值小的元素然后和左边下标所指元素进行交换

将右边元素交换到左边之后，再从左边开始比较

如果左边元素比基准值小，左边下标继续往后移动，之后遇到比基准值大的元素然后和右边下标所指元素进行交换

如果左边元素比基准值大，就和右边值交换，然后右边下标往前移

2.7.3代码

int Partition(int arr[], int left, int right)

{

int tmp = arr[left];

while (left < right)

{

while (left < right && arr[right] > tmp)

{

right–;

}

if (left == right)

{

break;

}

arr[left] = arr[right];

while (left < right && arr[left] <= tmp)

{

left++;

}

if (left == right)

{

break;

}

arr[right] = arr[left];

}

arr[left] = tmp;//arr[right]==tmp也可以，因为退出循环之后left=right

return left;

}

void Quick(int arr[], int left, int right)

{

if (left < right)

{

int tmp=Partition(arr, left, right);

Quick(arr, left, tmp-1);

Quick(arr, tmp + 1, right);

}

}

void Quick_sort(int arr[], int n)

{

Quick(arr, 0, n – 1);

}

2.7.4快速排序的优化

因为快速排序越乱排序的效率越高，数据越整齐就相当于选择排序，从而导致时间复杂度O(n^2),所以快速排序的优化：

①如果数据量特别的小，直接选择冒泡排序或者直接插入排序算法

②三数取中法：取第一个值和最中间的值、最后一个值进行判断，将不大不小的那个值当作快排的基准值

③主要针对快排已经有序，有了防止完全有序，我们自己可以打乱一下

（优化部分在Quick函数中，因此下面只给出了Quick函数的优化代码，其他代码同上，此处省略）

void ThreeNumGetMid(int arr[], int left, int mid, int right)

{

if (arr[mid] > arr[left] && arr[mid]<arr[right] || arr[mid]>arr[right] && arr[mid] < arr[left])

{

int tmp = arr[left];

arr[left] = arr[mid];

arr[mid] = arr[left];

}

if (arr[right] > arr[left] && arr[right] < arr[mid] || arr[right]<arr[left] && arr[right]>arr[mid])

{

int tmp = arr[left];

arr[left] = arr[right];

arr[right] = tmp;

}

}

void Quick(int arr[], int left, int right)

{

//第一处优化：

if (left – right <= 100)

{

return Bubble_Sort(arr, right – left);

}

//第二处优化：

int mid = (right – left) / 2;

ThreeNumGetMid(arr, left,mid, right);

if (left < right)

{

int tmp=Partition(arr, left, right);

Quick(arr, left, tmp-1);

Quick(arr, tmp + 1, right);

}

}

2.7.5用（栈）非递归的形式去实现上述的Quick函数

void Quick(int arr[], int left, int right)

{

stack<int>st;

int tmp = Partition(arr, left, right);

if (left < tmp-1)

{

st.push(left);

st.push(tmp – 1);

}

if (tmp + 1 > right)

{

st.push(tmp + 1);

st.push(right);

}

while (!st.empty())

{

int lf, rt;//lf,rt分别代表下一次patition是的left,right

rt=st.top();

st.pop();

lf = st.top();

st.pop();

int par = Partition(arr, lf, rt);

if (lf < par – 1)

{

st.push(lf);

st.push(par – 1);

}

if (par + 1 > rt)

{

st.push(par + 1);

st.push(rt);

}

}

}

2.8基数排序（桶排序）

2.8.1奇数排序的基本思想：

低位优先，所有数据从低位（个位）开始，一次放入10个桶内（入队），再从桶里取出，直到完全有序

2.8.2代码

int CountNum(int arr[], int n)

{

int max = INT_MIN;

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

{

if (arr[i] > max)

{

max = arr[i];

}

}

int count = 0;

while (max != 0)

{

++count;

max /= 10;

}

return count;

}

int GetNum(int arr, int k)

{

for (int i = 0; i < k; i++)

{

arr /= 10;

}

arr = arr % 10;

return arr;

}

void Redix(int arr[], int n, int k)

{

//定义桶10个，每个桶可以存放的元素有20个

int bucket[10][20] = { 0 };

int num[10] = { 0 };//记录每个桶里面元素的个数

//获取当前位数的数字，并将其放入对应的桶中

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

{

int index = GetNum(arr[i], k);

bucket[index][num[index]] = arr[i];

++num[index];

}

//将数据从桶中取出

int m = 0;

for (int i = 0; i < 10; i++)

{

for (int j = 0; j < num[i]; j++)

{

arr[m++] = bucket[i][j];

}

}

}

void Redix_Sort(int arr[], int n)

{

//获取最大的位数从而作为循环的条件（表明需要进行多少次的进出桶）

int count = CountNum(arr, n);

for (int i = 0; i < count; i++)

{

Redix(arr, n, i);//表示从个位开始，每循环一次，就进行一趟桶排序

}

}

2.8.3使用队列实现上述的Redix函数

void Redix(int arr[], int n, int k)

{

queue<int>qu[10];

//入桶

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

{

int index = GetNum(arr[i], k);

qu[index].push(arr[i]);

}

//出桶

int m = 0;

for (int i = 0; i < 10; i++)

{

while (!qu[i].empty())

{

arr[m++] = qu[i].front();

qu[i].pop();

}

}

}