排序是算法中的重要内容，通过复习排序可以对算法的基本思路和分析方法进行把握。利用c复习排序算法还可以同时复盘c的内存使用方法。
本文依次实现了冒泡排序，插入排序，选择排序，归并排序，快速排序，希尔排序，桶排序和基数排序，最后分析了它们的算法复杂度。 动态数组和排序算
此前在文章中我们已经介绍了[如何实现动态数组]，这里的排序是以动态数组为对象进行的。
排序算子定义了顺序的概念，对于数组a[0:n-1], 若存在cmp(a[i], a[i-1)) == true，则(a[i], a[i+1])为顺序对，反之为逆序对。排序的过程就是消除逆序对的过程。
//sort.h
#include <stdbool.h>
#include "vector.h"
typedef bool (*cmp_func) (void *, void *);
//sort.c
static bool less_val_cmp(void *lhs, void *rhs){
if((int)lhs <= (int)rhs){
return true;
}else{
return false;
}
}
static bool more_val_cmp(void *lhs, void *rhs){
if((int)lhs >= (int)rhs){
return true;
}else{
return false;
}
}
static void swap(void **lhs, void **rhs){
void *tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
冒泡排序是一种直观的排序方法，通过n-1趟遍历，每次比较两个元素，每趟将最小的一个元素传递到最前，形成一个顺序区，最终所有元素都与其邻居保持顺序，完成排序。
void bubble_sort_vec(vector *v, cmp_func cmp){
bool do_swap = false;
//for each element in a[0:n-1)
for(int i = 0; i < v->len - 1; i++){
//bubble up the reverse order pair
for(int j = v->len - 1; j > 0; j--){
if(!cmp(v->items[j-1], v->items[j])){
swap(&v->items[j-1], &v->items[j]);
do_swap = true;
}
}
//if no reverse pair exist, target is already sorted
if(!do_swap)
break;
}
}
3. 插入排序
插入排序的思想也很直观，a[0,i)为顺序区，取a[i]，在顺序区中找个一个合适a[i]的位置进行插入，最终整个数据集合都是顺序区，完成排序。
void insert_sort_vec(vector *v, cmp_func cmp){
for(int i = 1; i < v->len; i++){
//first element in un-order region
void *key = v->items[i];
int j = i - 1;
//move elements in ordered region back by one if it is larger than to-
//insert one
while(j >= 0 && cmp(key, v->items[j])){
v->items[j+1] = v->items[j];
j--;
}
v->items[j+1] = key; //insert key
}
}
4. 选择排序
选择排序和插入排序的思想基本相同，都是维护一个“顺序区”，不同的是，插入排序通过调整“顺序区”来维护，选择排序则通过选择一个“非顺序区”中最大的元素来维护新“顺序区”。
void select_sort_vec(vector *v, cmp_func cmp){
for(int i = 0; i < v->len; i++){
int min_idx = i;
void *min_key = v->items[i];
//select the min element in 'unorder' region
for(int j = i; j < v->len; j++){
if(cmp(v->items[j], min_key)){
min_idx = j;
min_key = v->items[j];
}
}
//put min element in the back of 'ordered region'
swap(&v->items[i], &v->items[min_idx]);
}
}
5. 快速排序
快速排序相比之前的三种排序方法复杂一些，它使用了分而治之的思路，对于数据集合的每个区间，取出一个划分位(parition)，移动集合元素，使得划分位前的元素小于划分位，之后的元素大于划分位。同时推广这种方法于划分位前后子区间。
首先是划分区间[low, high]，任意取一个划分位(这里取的是末尾)，遍历区间内的元素，若元素小于划分位，将其交换到前半区间(i)，最终，将划分位交换到前半区间的末尾，划分完成，前半区间的元素皆小于划分位，而后半区间的元素皆大于划分位。
static int partition(vector *v, cmp_func cmp,
int low, int high){
void *pivot = v->items[high];
int i = low;
for(int j = low; j < high; j++){
if(!cmp(pivot, v->items[j])){
swap(&v->items[i], &v->items[j]);
i++;
}
}
swap(&v->items[i], &v->items[high]);
return i;
}
分而治之，将划分推广到前半区间和后半区间。
static void quick_sort_vec_helper(vector *v, cmp_func cmp,
int low, int high){
if(low < high){
int pi = partition(v, cmp, low, high);
quick_sort_vec_helper(v, cmp, low, pi-1);
quick_sort_vec_helper(v, cmp, pi+1, high);
}
}
void quick_sort_vec(vector *v, cmp_func cmp){
quick_sort_vec_helper(v, cmp, 0, v->len-1);
}
6. 归并排序
归并排序同样使用了“分而治之”的思路，将数据集合划分直到子集合只有一个元素，然后在归并子集合的过程中完成排序。
首先实现的是按顺序归并两个子集合。
static void merge(vector *v, cmp_func cmp, int low, int mid,
int high){
int llen = mid - low + 1,
rlen = high - mid;
void *L[llen], *R[rlen];
//copy elements to left and right set
memmove(L, v->items + low, sizeof(void*)*llen);
memmove(R, v->items + mid + 1, sizeof(void*)*rlen);
//merge two set
int i = 0, j = 0, idx = low;
while(i < llen && j < rlen){
if(cmp(L[i], R[j])){
v->items[idx++] = L[i++];
}else{
v->items[idx++] = R[j++];
}
}
//copy the remain set after merge
if(i < llen){
memmove(&v->items[idx], &L[i], sizeof(void*)*(llen - i));
}else if(j < rlen){
memmove(&v->items[idx], &R[j], sizeof(void*)*(rlen - j));
}
}
划分是将集合划分成等长的左右两份，分别进行排序后归并。
static void merge_sort_vec_helper(vector *v, cmp_func cmp,
int low, int high){
if(low < high){
int mid = low + (high - low)/2;
merge_sort_vec_helper(v, cmp, low, mid);
merge_sort_vec_helper(v, cmp, mid+1, high);
merge(v, cmp, low, mid, high);
}
}
void merge_sort_vec(vector *v, cmp_func cmp){
merge_sort_vec_helper(v, cmp, 0, v->len - 1);
}
7. 希尔排序
希尔排序是插入排序的一个变种，它的特点是允许位置相距很远的元素进行交互，从而减少元素位置移动的次数。
void shell_sort_vec(vector *v, cmp_func cmp){
//for each kind of iter gap
for(int gap = v->len/2; gap > 0; gap /= 2){
//for each element in the first gap region
for(int i = gap; i < v->len; i += 1){
void *key = v->items[i];
int j = i;
//exchange with 'gap' far element
for(; j >= gap && cmp(key, v->items[j - gap]); j -= gap){
v->items[j] = v->items[j-gap];
}
v->items[j] = key;
}
}
}
8. 桶排序
void bucket_sort_fvec(fvector *v, float_cmp_ptr cmp) {
//create buckets for count sorting
const int BUCKET_NUM = 10;
fvector buckets[BUCKET_NUM];
for (int i = 0; i < BUCKET_NUM; i++) {
init_fvec(&buckets[i]);
}
//put all elements into bukcets
int ix = 0;
for (int i = 0; i < v->len; i++) {
ix = v->items[i] * BUCKET_NUM;
if (ix < 0 || ix > BUCKET_NUM)
err_exit(BAD_INDEX);
push_back_fvec(&buckets[ix], v->items[i]);
}
//sort each buckets
for (int i = 0; i < BUCKET_NUM; i++) {
select_sort_fvec(&buckets[ix], cmp);
}
//merge all buckets
ix = 0;
for (int i = 0; i < BUCKET_NUM; i++) {
for (int j = 0; j < buckets[i].len; j++) {
v->items[ix++] = buckets[i].items[j];
}
}
}
9.基数排序
//sort arry according to the digit represented by exp
void count_sort(vector *v, int exp) {
int bucket_num = 10;
int *output = calloc(v->total, sizeof(int)), //output array
*count = calloc(bucket_num, sizeof(int));
//store the count of occurences
for (int i = 0; i < v->total; i++)
count[GET_DIGIT(VECTOR_GET(*v, int, i), exp)]++;
//make count[i] contain the actual position of this digit
// in output
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
//build the output array
for (int i = v->total - 1; i >= 0; i--) {
int digit = GET_DIGIT(VECTOR_GET(*v, int, i), exp);
output[digit - 1] = (int)v->items[i];
count[digit]--;
}
//copy ouput array to dst
for (int i = 0; i < v->total; i++)
v->items[i] = (void *)(long)output[i];
free(output);
free(count);
}
void radix_sort_vec(vector *v) {
int mx = get_max_ele(v);
//start sorting from less significant digit
for (int exp = 1; mx / exp > 0; exp *= 10)
count_sort(v, exp);
}
代码清单：https://github.com/KevinACoder/Learning/blob/master/ds/sort.h
网友评论