时间复杂度O(n2)的算法
冒泡排序
冒泡排序是入门级的算法，原理是利用当前值和后值的大小比较，交换位置，每一次循环把没有排序的数据中的最大值移动到未排序部分的最后一个，用冒泡来命名还是很形象的，最大的数据最轻，一步一步上浮到表面，即尾巴。通常有三种写法：
- 一边比较，一般移动最大值，保证每一轮都能把最大值移动到最后。
- 第二种写法在第一种的基础上加一个是否有交换的标志，当某一次循环全程没有发生交换，说明未排序部分已经是有序了，直接完成排序，没有改变倒序数组这种最差情况的时间复杂度。
- 第三种在第二种写法的基础上进一步优化，除了加一个判断没有发生交换的标志，还优化了内循环的结尾，第一种写法的内循环结尾是arrary.length - 1 - i，我们可以记录内循环中最后一次交换的位置，如果这个位置不在结尾处，说明这个位置到结尾的顺序是正确的，下一次内循环的结尾可以设为这个位置，除了最坏情况，还是可以减少时间复杂度的。算法流程如下：
以下是三种算法的C语言实现
void swap(int *arrary, int i, int j) {
int tmp = arrary[i];
arrary[i] = arrary[j];
arrary[j] = tmp;
}
void bubbleSortA(int *arrary, int len) {
for (int i = 0; i < len - 1; i++){
for (int j = 0; j < len - i - 1; j++) {
if (arrary[j] > arrary[j+1]) {
swap(arrary, j, j+1);
}
}
}
}
void bubbleSortB(int *arrary, int len) {
bool swapYes = false;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len -i - 1; j++) {
if (arrary[j] > arrary[j+1]) {
swap(arrary, j, j+1);
swapYes = true;
}
}
if (!swapYes) break;
swapYes = false;
}
}
void bubbleSortC(int *arrary, int len) {
bool swapYes = false;
int swapTail = len - 1;
int swapTailTmp = 0;
while (!swapYes) {
for (int i = 0; i < swapTail; i++) {
if (arrary[i] > arrary[i+1]) {
swap(arrary, i, i + 1);
swapTailTmp = i + 1; //临时记录最后一次交换数据的位置
swapYes = true;
}
}
swapTail = swapTailTmp; //下一次循环的尾巴
if (!swapYes) break;
swapYes = false;
}
}选择排序
选择排序的思路比较简单，每一轮循环，找到最小值，交换最小值位置和队首位置，队首后移。实现示意图如下：
实现代码如下：
void selectionSort(int *arrary, int len) {
int posMin = 0, minValue = arrary[0];
for (int i = 0; i < len - 1; i++) {
int posMin = i, minValue = arrary[i];
for (int j = i; j < len; j++) {
if (arrary[j] < minValue) {
minValue = arrary[j];
posMin = j;
}
}
swap(arrary, i, posMin);
}
}二元选择排序
选择的排序的核心是在未排序的数据中，选取最小值与未排序数据队首交换，有一种优化思路是同时筛选最大值插入未排序数据队尾。实现代码如下：
void selectionSortBin(int *arrary, int len) {
for (int i = 0; i < len / 2; i++) {
int posMin = i, posMax = len - i - 1;
int minVAlue = arrary[posMin], maxValue = arrary[posMax];
for (int j = i; j < len - i; j++) {
if (arrary[j] < minVAlue) {
minVAlue = arrary[j];
posMin = j;
}
if (arrary[j] > maxValue) {
maxValue = arrary[j];
posMax = j;
}
}
//当最大值和最小值相等的时候说明剩下的数据完全一样
if (maxValue == minVAlue) break;
swap(arrary, i, posMin);
//可能存在最大值就是i，上面i和posMin的值交换了，需要判断
if (posMax == i) {
swap(arrary, len - i - 1, posMin);
}
else {
swap(arrary, len - i - 1, posMax);
}
}
}选择排序的比较分为三个部分，i、j和value的比较，i的比较在数组较大的时候，相对于后面两个可以忽略，所以我们只考虑j和value的比较。对于二元选择排序和选择排序，前者的比较次数是(1/4n^2+1/2n^2)
，即3/4n^2，后者的比较次数(1/2n^2+1/2n^2)，即n^2，虽然能够减少比较次数，但是并没有改变时间复杂度。
排序算法稳定性
这个很好理解，比较一下冒泡排序和选择排序对于相同数据的处理方式即可，后者无法保证相同数据的顺序没有变化，这种特性就是排序的不稳定性。因为实际的应用中，可能会有多种排序条件，对于某一商品，有一组数据记录了销量和单价，按销量进行排序，销量相同按价格排序。先按照单价进行排序，再按照销量排序，第二步销量排序一旦不稳定，会导致价格顺序变化，达不到排序目的。不稳定排序可以使用新建存储存储数据的方式解决不稳定性。
插入排序
插入排序算法的思路是一个一个的插入数据，插入的数据必须一次性插到已排序队列的准确位置。实现过程示意图如下：
一种交换插入排序的实现代码如下：
void insertSort(int *arrary, int len) {
for (int i = 1; i < len; i++) {
int j = i - 1;
int value = arrary[i];
while (j >= 0 && arrary[j] > arrary[j+1]) {
arrary[j+1] = arrary[j];
arrary[j] = value;
j--;
}
}
}上面的算法是每次交换两个相邻的数据，在此基础上可以采用移动插入的方法，就是只要没找到目标数据的位置，就把比较过的位置后移一格，直到找到合适的位置插入目标数据。实现代码如下：
void insertSortB(int *arrary, int len) {
for (int i = 1; i < len; i++) {
int j = i - 1;
int value = arrary[i];
while (j >= 0 && arrary[j] > value) {
arrary[j+1] = arrary[j];
j--;
}
arrary[j+1] = value;
}
}时间复杂度O(nlogn)的算法
希尔排序
希尔排序是首批将时间复杂度降到O(n2)以下的算法，希尔算法是对插入排序的一种优化。要想理解希尔排序，首先需要了解排序算法的核心，排序算法的核心是消除“逆序对”，什么是“逆序对”？A和B，前值大于后值，那么<A,B>就是一个逆序对，前面的三种O(n2)算法，都是每次比较相邻元素，每比较一次消除一个逆序对，那么要是比较一次可以消除多个逆序对的话，是不是就可以大大减少时间复杂度。这就是希尔排序的核心思想，通过增大比较间隔（相邻元素比较间隔是1），有机会通过一次比较消除多个逆序对。以[6,5,8,7,2,3,1,10,4,9]为例的排序示意图如下：
增量序列
定义增量序列：Dm>Dm-1...>D1
从上述的过程可以看出，每一次的间隔范围都在缩小，每一次的插入排序数据数目都在增大，希尔把这个间隔<5,2,1>称为希尔增量序列，用的N/2实现的，后面有研究发现如果这个序列不是互质的，会出现小增量的时候不起作用，比如<1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16>这样的数组采用希尔增量序列<8,4,2,1>的时候，前三个增量都不起作用，只有最后<1>起作用，而<1>就是插入排序了，这样的希尔排序反而比插入排序多了很多无效操作。因此，增量序列的选择非常重要，有几个比较有名的增量序列如下：
- Hibbard增量序列 2k - 1;
- Knuth增量序列 D1 = 1; Dk+1 = 3k + 1;
- sedgewick增量序列通过9*4k - 9*2k + 1计算得到;
下面是采用希尔增量队列的希尔排序的实现代码:
void shellSort(int *arrary, int len) {
for (int gap = len / 2; gap > 0; gap/=2) { // 增量序列设置方法
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < len; j+=gap) {
int k = j - gap;
int value = arrary[j];
while (arrary[k] > value && k >= 0) {
arrary[k+gap] = arrary[k];
arrary[k] = value;
k-=gap;
}
}
}
}
}上面的代码三层的循环，第一层是gap序列，第二层是子数组的起始元素，第三层就是把插入排序的间隔1换成gap进行插入排序。假设对于12个元素的数组，第一层gap是<6,3,1>，第二层相应是<0,1,2,3,4,5> <0,1,2> <0>，第三层就是每个第二层的开头元素+gap进行插入排序了。这是人类比较好理解的思路，处理多个跳跃的不连续数组，计算机更喜欢连续访问数组内容，我们可以代码进行优化，从gap位置开始连续进行插入排序，代码如下：
void shellSortB(int *arrary, int len) {
for (int gap = len / 2; gap > 0; gap/=2) {
for (int i = gap; i < len; i++) {
int currentValue = arrary[i];
int prePos = i - gap;
while (arrary[prePos] > currentValue && prePos >= 0) {
arrary[prePos+gap] = arrary[prePos];
arrary[prePos] = currentValue;
prePos-=gap;
}
}
}
}希尔排序小结
- 希尔排序是对插入排序的优化，但是希尔排序不是稳定性排序算法，因为在增量序列值较大的时候会改变想用数值的位置。
- 增量序列的不同会大大影响希尔排序的计算效率，第一层循环的可以实现不同的增量序列。
- 希尔序列不需要考虑数据长度的奇偶性，因为增量序列值为1的时候会进行一次全插入排序。
- 希尔排序在O(n2)算法上做出了突破，是一个承上启下的算法。
堆排序
堆排序是利用堆这种数据结构设计的排序算法，堆排序是一种选择排序，最好、最坏和平均时间复杂度都是O(nlogn)，也是一种不稳定排序。堆是具有以下性质的完全二叉树：
- 大顶堆，每个节点的值大于等于其左右子节点的值。
- 小顶堆，每个节点的值小于等于其左右子节点的值。
- 不要求左右子节点值得大小比较
- 对于n个元素的完全二叉树，第一个非叶节点是n/2 - 1, 第i个节点的左子节点是2i+1，右子节点是左子节点+1
因为是将堆顶元素和结尾叶节点的交换，所以升序排序用大顶堆，降序排序用小顶堆。堆排序的基本思想（升序）
- 将待排序序列构造成一个大顶堆
- 大顶堆的堆顶即是最大值，和末尾元素交换
- 把上一步的堆顶元素排除在外，重新调整大顶堆，和新的堆末尾元素交换
- 循环上述步骤得到有序序列
整个过程中，关键点是调整大顶堆函数中的递归调用，堆中的数据最开始的时候是无序排列的，每一次的调整都是在一个非叶节点和它的子节点中进行的，假设这时候根节点root小于子节点left，两者发生了交换，这时候root的值交换到了left的位置，因为现在的root是第一次比较，并不像left是经过比较升上来的，所以root即使回到了left的位置，这个位置也可能不适合它，也需要继续去判断自己是否属于这个位置，直到找到自己合适的位置，这就是递归的由来。下面是引用了leetcode的形象描述：
构建大顶堆的过程就是一堆数字比赛谁更大。比赛过程分为初赛、复赛、决赛，每场比赛都是三人参加。但不是所有人都会参加初赛，只有叶子结点和第一批非叶子结点会进行三人组初赛。初赛的冠军站到三人组的根结点位置，然后继续参加后面的复赛。
而有的人生来就在上层，比如李小胖，它出生在数列的第一个位置上，是二叉树的根结点，当其他结点进行初赛、复赛时，它就静静躺在根结点的位置等一场决赛。
当王大强和张壮壮，经历了重重比拼来到了李小胖的左右子树结点位置。他们三个人开始决赛。王大强和张壮壮是靠实打实的实力打上来的，他们已经确认过自己是小组最强。而李小胖之前一直躺在这里等决赛。如果李小胖赢了他们两个，说明李小胖是所有小组里最强的，毋庸置疑，他可以继续坐在冠军宝座。
但李小胖如果输给了其中任何一个人，比如输给了王大强。王大强会和张壮壮对决，选出本次构建大顶堆的冠军。但李小胖能够坐享其成获得第三名吗？生活中或许会有这样的黑幕，但程序不会欺骗我们。李小胖跌落神坛之后，就要从王大强的打拼路线回去，继续向下比较，找到自己真正实力所在的真实位置。
下面是堆排序的排序示意图：
构建大顶堆:
调整大顶堆：
代码实现：
void heapSort(int *arrary, int arrarySize) {
buildMaxHeadHeap(arrary, arrarySize);
for (int i = arrarySize - 1; i > 0; i--) {
swap(arrary, 0, i);
adjustHeap(arrary, 0, i);
}
}
void buildMaxHeadHeap(int *arrary, int arrarySize) {
for (int i = arrarySize / 2 - 1; i>= 0; i--) {
adjustHeap(arrary, i, arrarySize);
}
}
void adjustHeap(int *arrary, int root, int arrarySize) {
int left = 2*root + 1;
int right = left + 1;
int largest = root;
if (left < arrarySize && arrary[left] > arrary[largest]) {
largest = left;
}
if (right < arrarySize && arrary[right] > arrary[largest]) {
largest = right;
}
if (largest != root) {
swap(arrary, root, largest);
adjustHeap(arrary, largest, arrarySize);
}
}快速排序
快速排序的基本思想：
- 从数组中取出一个基数（pivot）
- 遍历数组，将数组分为大于基数和小于基数的两个区域
- 将两个区域的作为两个子数组继续排序，使用递归，继续分割，一直到分组只有两个元素的时候开始回溯
快速排序在每一次分区过程中，最好的情况是基数不是最大值也不是最小值，第一层到第N层，分别排好1、2、4、8...个基数，总的遍历次数是logn，最差是对于有序数组，每次都只能排号一个基数，总遍历次数是n，每轮交换位置的时间复杂度是n，所以快排的时间复杂度是nlogn~n2，平均时间复杂度是nlogn。
数据分区的算法有三种：
- hoare方法，快排发明者使用的方法，也是一种双指针方法，left从左往右找到一个大于基数的数据，right从右往左找到一个小于基数的数据，两者交换，直到left=right，判断一下left的值和基数值得大小，比基数大直接基数和left-1交换，如果left小于基数，则基数和left交换。
- 挖坑法，也是一种双指针方法，把基数作为一个hole，保留一下值，然后从right右往左找小于基数的值，和hole交换，left从左向右找一个大于基数的值，和hole交换，循环往复直到right=left，hole就是基数的位置。
- 快慢指针法，取最左边的数为key，定义两个快慢指针，都从key的下一位往右走，fast每走一步判断一下它指向的元素是否小于key，若小于则交换fast和slow位置的元素，并且让slow向前走，直到fast走到底，结束循环。最后让slow和key位置的值交换。再返回key的位置。
hoare分区算法的示意图如下，其他两种分区算法都是N遍历的算法，时间复杂度一样，实现过程不一样。
三种数据分区方法的实现代码如下：
//hoare方法
int partitionA(int *arrary, int start, int end) {
int pivot = arrary[start];
int left = start, right = end;
while (left < right) {
while (left < right && arrary[left] <= pivot) left++;
while (left < right && arrary[right] >= pivot) right--;
if (left != right) {
swap(arrary, left, right);
}
}
if (arrary[left] > pivot) {
swap(arrary, left - 1, start);
return left - 1;
}
else {
swap(arrary, left, start);
return left;
}
}
//挖坑法，双向移动坑位，最后把pivot的值给hole，返回hole
int partitionB(int *arrary, int start, int end) {
int left = start, right = end;
int hole = start;
int pivot = arrary[start];
while (left < right) {
while (left < right && arrary[right] >= pivot) right--;
if (right != left) {
arrary[hole] = arrary[right];
hole = right;
}
while (left < right && arrary[left] <= pivot) left++;
if (right != left) {
arrary[hole] = arrary[left];
hole = left;
}
}
arrary[hole] = pivot;
return hole;
}
//快慢指针法
int partitionC(int *arrary, int start, int end) {
int slow = start, fast = start + 1;
int pivot = arrary[start];
while (fast <= end) {
if (arrary[fast] < pivot) {
swap(arrary, slow, fast);
slow++;
fast++;
}
}
return slow;
}
void quickSortMain(int *arrary, int start, int end) {
int pivotPos = partitionB(arrary, start, end);
//某一分区至少两个元素才排序
if (pivotPos - start > 1) quickSortMain(arrary, start, pivotPos - 1);
if (end- pivotPos > 1 ) quickSortMain(arrary, pivotPos + 1, end);
}
//为了和前面的排序函数用法统一
void quickSort(int *arrary, int arrarySize) {
int start = 0, end = arrarySize - 1;
quickSortMain(arrary, start, end);
}快速排序的优化
- 三数取中。基数的选择影响了时间复杂度，每一次都只能决定一个基数效果就很差，随机选一个可以，也可以头尾中三个位置大小比较选择中间大小的作为基数，避免只能决定一个基数。
- 小区间选择排序。当区间内元素比较少的时候，继续调用递归，会产生大量的资源消耗，尤其接近最后几层的时候，可以选择在分区元素较少的时候时候选择排序来排序。
- 混乱数据。数据可能本身就是带顺序的，快速排序这时候效果很差，可以使用一些函数，让数据随机化。
非递归实现快速排序
上面的快速排序递归实现是通过不断的去对新的区间进行划分，递归的原理和栈的先进后出的规则很像，我们可以通过对区间的不断进栈出栈来完成新的区域划分，即可不用递归实现不同区间的划分了。比如对于[0,1,2,3,4,5,6]（序号）这个数组，我们先调用一次函数找出pivotPos [2]，那么左区间就是[0,1]，右区间就是[3,6]，我们把这两组数据压进栈里面，然后出栈[3,6]进行还分，假设这时候新的pivotPos是4，那么新的区间就是[3,3]和[5,6]，前者不用压栈，后者继续压栈，一直到右区间无法压栈了，未排序区间都保存在了栈中，最后挨个出栈进行排序即可。
//定义一个整数数组栈和入栈、出栈、取栈顶元素
typedef struct stackNode {
struct stackNode *next;
int value;
} stackNode;
void stackPush(stackNode *st, int value) {
stackNode *node = malloc(sizeof(stackNode));
node->next = st->next;
node->value = value;
st->next = node;
}
void stackPop(stackNode *st) {
stackNode *node = st->next;
st->next = st->next->next;
free(node);
}
int stackTop(stackNode *st) {
return st->next->value;
}
void quickSortStackMain(int *arrary, int start, int end) {
stackNode *st = malloc(sizeof(stackNode));
st->next = NULL;
stackPush(st, start);
stackPush(st, end);
while (st->next != NULL) {
end = stackTop(st);
stackPop(st);
start = stackTop(st);
stackPop(st);
int pivotPos = partitionA(arrary, start, end);
if (pivotPos - start > 1) {
stackPush(st, start);
stackPush(st, pivotPos - 1);
}
if (end- pivotPos > 1) {
stackPush(st, pivotPos + 1);
stackPush(st, end);
}
}
}
void quickSortStack(int *arrary, int arrarySize) {
int start = 0, end = arrarySize - 1;
quickSortStackMain(arrary, start, end);
}归并排序
有刷过leetcode合并多个有序数组的小伙伴应该知道合并多个有序数组的方法，于是可以采用类似上述快速排序的分割思路，我们对原来的数组进行等分分割，当分割到长度为1的时候，就是一个一个有序数组了，这时候对这一个一个有序数组进行合并，分割过程的时间复杂度是lgn，遍历的时间复杂度是n，归并排序的时间复杂度就是nlgn，没有最差情况，也是一种稳定排序算法。
归并排序的思路：
实现代码：
void mergeSortMain(int *arrary, int *ret, int start, int end) {
if (start >= end) return;
int mid = ((end - start) >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
mergeSortMain(arrary, ret, start1, end1);
mergeSortMain(arrary, ret, start2, end2);
int k = start;
//合并两个有序数组的三个while函数
while (start1 <= end1 && start2 <= end2) {
ret[k++] = arrary[start1] < arrary[start2] ? arrary[start1++] : arrary[start2++];
}
while (start1 <= end1) {
ret[k++] = arrary[start1++];
}
while (start2 <= end2) {
ret[k++] = arrary[start2++];
}
//将排序好的
for (k = start; k <= end; k++) {
arrary[k] = ret[k];
}
}
void mergeSort(int *arrary, int arrarySize) {
int ret[arrarySize];
mergeSortMain(arrary, ret, 0, arrarySize - 1);
}归并排序不存在原位排序的情况，不使用辅助数组ret的话，在合并的时候就需要和插入排序一样，去调整某一主子数组的后续数据，实际就是插入排序。
时间复杂度O(nlogn)的算法小结
这一小节讲解了希尔排序、堆排序、快速排序和归并排序，这些排序算法本质上是比较排序。n个数据，它可能出现的排列方式是n!，可以用决策树来理解，树的高度h就是得到我们想要结果的时间复杂度，排列方式就是数的叶节点，对于h高度的树而言，它的叶节点数l最多是2h个，所以2h >= l >= n!，得到h>= log(n!)， log(n!)就是O(nlgn)。
综上可以得到结论比较排序的最优时间复杂度就是nlgn，不可能突破，其中堆排序和归并排序是最佳的比较排序算法，时间复杂度最好和最差都是nlgn。
时间复杂度O(n)的算法
计数排序
计数排序是一种特殊的O(n+k)的排序算法，k是排序数据的数据范围，适用于海量的数据数量，但是数据范围很小的排序案例(几十万的学生，考试分数0~100)，常数k可以忽略，就是O(n)。之所以能突破nlgn等比较排序，是因为计数排序全程没有比较，一次性把数据放到对应位置，排序过程中不会打乱相同数据的顺序，是稳定性算法。
算法思路如下：
- 遍历数组找出数据范围的最大值max和最小值min
- 定义并生成一个max-min+1大小的数组，下标和数据对应，数值对应数据出现次数
- 对上述的数组进行处理，将数值替换成该下标前的所有数组数据的和（数组记录了在正确排序中第一次出现的位置）
- 遍历数组，第一次出现某元素，第三步数组中的值就是该元素的正确排序，出现一次，第三步的数组的值加1即可完成正确排序
计数排序示意图如下：
计算排序实现代码：
#include
void countingSort(int *arrary, int arrarySize) {
int max = arrary[0], min = arrary[0];
for (int i = 0; i < arrarySize; i++) {
if (arrary[i] > max) {
max = arrary[i];
}
else {
min = arrary[i] < min ? arrary[i] : min;
}
}
int lenOfCountingArrary = max - min + 1;
int *arraryAppearCounts = calloc(lenOfCountingArrary, sizeof(int));
for (int j = 0; j < arrarySize; j++) {
arraryAppearCounts[arrary[j] - min]++;
}
int *arraryFirstAppear = calloc(lenOfCountingArrary, sizeof(int));
int sum = 0; //记录循环当前位置前所有出现数据的次数和
int tmp = arraryAppearCounts[0]; //记录当前位置的数据出现次数
for (int m = 1; m < lenOfCountingArrary; m++) {
sum += tmp;
tmp = arraryAppearCounts[m];
arraryFirstAppear[m] = sum;
}
int ret[arrarySize];
for (int k = 0; k < arrarySize; k++) {
ret[arraryFirstAppear[arrary[k] - min]] = arrary[k];
arraryFirstAppear[arrary[k] - min]++;
}
for (int l = 0; l < arrarySize; l++) {
arrary[l] = ret[l];
}
free(arraryAppearCounts);
free(arraryFirstAppear);
} 基数排序
基数排序是利用关键字进行排序的，比如对于997，999，666，866这几个数字进行排序，都是相同的位数，我们可以先比较第一位9>8>6，[997,999,866,666]，然后对第二位进行比较，顺序不变，对最后一位进行比较9>7,[999,997,866,666]，得到正确的顺序。这种从最高位进行比较的方法是MSD（Most significant digital），最高位优先法，与之对应的是LSD（Least significant digital）。LSD一般比MSD使用更多，MSD高位决定了不同高位间的顺序是不能改变的，往低位走的过程中，只能排序相同高位间的数据，需要调用递归来实现，比较复杂，而且还占用额外的空间，采用LSD从低到高的话，一视同仁，位数不足补位0也不会影响顺序。
LSD方法思路如下：
- 找出最大值
- 计算最大值的位数
- 从低到高模运算取基数，基数范围在[0-9]范围内，调用计数排序
LSD基数排序的思路图如下：
LSD基数排序实现代码如下：
#include "../include/sort_n_counting.h"
#include
void radixSort(int *arrary, int arrarySize) {
//找出最大值
int max = arrary[0];
for (int i = 0; i < arrarySize; i++) {
max = arrary[i] > max ? arrary[i] : max;
}
//计算最大值长度
int len = 0;
while (max != 0) {
max/=10;
len++;
}
//定义基数数组、计算排序的计数数组和结果数组
int arraryCounting[10] = {0};
int ret[arrarySize];
int dev = 1;
for (int radixLevel = 0; radixLevel < len; radixLevel++) {
//生成基数数组
for (int j = 0; j < arrarySize; j++) {
int radix = (arrary[j] / dev) % 10;
arraryCounting[radix]++;
}
//记录元素最后一次出现的位置的后一位
for (int k = 1; k < 10; k++) {
arraryCounting[k] += arraryCounting[k-1];
}
//计数排序
for (int m = arrarySize - 1; m >= 0; m--) {
int radix = (arrary[m] / dev) % 10;
ret[--arraryCounting[radix]] = arrary[m];
}
//ret数组数据复制给arrary
for (int n = 0; n < arrarySize; n++) {
arrary[n] = ret[n];
}
//计数数组归0
for (int l = 0; l < 10; l++) {
arraryCounting[l] = 0;
}
dev*=10;
}
} 上面的LSD代码是针对正整数排序的，如果是排序数据有负数，可以采用所有数据加上最小负值的绝对值将数据全部转换成正整数进行排序，但是这种加和的方式可能会导致数据越界！可以换一种思路，扩展计算数组[0,9]到[0,18]，用于统计基数[-9,9]。实现代码如下：
void radixSortAll(int *arrary, int arrarySize) {
int max = arrary[0];
for (int i = 0; i < arrarySize; i++) {
max = abs(arrary[i]) > max ? abs(arrary[i]) : max;
}
int len = 0;
while (max != 0) {
max/=10;
len++;
}
int arraryCounting[19] = {0};
int ret[arrarySize];
int dev = 1;
for (int radixLevel = 0; radixLevel < len; radixLevel++) {
for (int j = 0; j < arrarySize; j++) {
int radix = (arrary[j] / dev) % 10 + 9;
arraryCounting[radix]++;
}
for (int k = 1; k < 19; k++) {
arraryCounting[k] += arraryCounting[k-1];
}
for (int m = arrarySize - 1; m >= 0; m--) {
int radix = (arrary[m] / dev) % 10 + 9;
ret[--arraryCounting[radix]] = arrary[m];
}
for (int n = 0; n < arrarySize; n++) {
arrary[n] = ret[n];
}
for (int l = 0; l < 19; l++) {
arraryCounting[l] = 0;
}
dev*=10;
}
}桶排序
桶排序的思路是：
- 根据数据的最大值最小值范围将划分成n个子区间，子区间称为桶
- 遍历数组，将数字装入桶中
- 对桶内的数字单独排序，采用前面的排序算法
- 最后按顺序将所有桶内数据合并
桶排序应用比较少，从排序思路就会发现，当数据不均匀的时候，桶里的数据也会非常不均匀，最差的情况是数据几乎只在一个桶内。满足数据均匀这个前提之后，就要考虑下面两个因素： - 桶的数量多少合适。桶的数量少，单个桶里的数据多，时间复杂度受桶内排序算法影响大；桶的数量多，占用的内存大，还会出现很多的空桶，影响遍历桶的效率。
-
桶采取哪种数据结构。用数组存储的话，必须要面对最差的情况，所有数据存储在一个桶内，我们也没办法确认在哪个桶内，这样所有的桶的存储空间就需要和原数据一样大，空间复杂度很高。使用链表可以避免空间复杂度大的问题，但是链表的排序比数组的时间要长。
下面就用数组实现桶排序的代码：void bucketSort(int *arrary, int arrarySize) { int max = arrary[0], min = arrary[0]; for (int i = 0; i < arrarySize; i++) { if (arrary[i] > max) { max = arrary[i]; } else { min = arrary[i] < min ? arrary[i] : min; } } int range = max - min; int bucketAmount = 10; double gap = (double)range / (bucketAmount - 1); int buckets[bucketAmount][arrarySize]; int *bucketSize = calloc(arrarySize, sizeof(int)); for (int j = 0; j < arrarySize; j++) { int index = (int)((arrary[j] - min) / gap); buckets[index][bucketSize[index]++] = arrary[j]; } int index = 0; for (int k = 0; k < bucketAmount; k++) { if (bucketSize[k] == 0) continue; insertSortB(buckets[k], bucketSize[k]); for (int l = 0; l < bucketSize[k]; l++) { arrary[index++] = buckets[k][l]; } } }桶是一个二维数组，每个桶的容量都是arrarySize，可以用realloc来控制每个桶的大小，这样的方式是用时间换空间了，因为realloc的过程也会耗费比较多的时间，尤其是申请空间失败的，还得重新开辟内存空间，复制数组。