《C语言实现各种排序算法》

一、排序

在生活中各种场景中都会有排序的身影存在，在网购时会有价格排序，在学校中会有程序排序，在游戏中会有段位的排序等。

1、排序的各种方式分类

这些排序的效率各有不同

二、插入排序

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。

1、直接插入排序

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移

代码实现：

void InsertionSort(int* arr, int n)
{int i = 0;int j = 0;for ( i = 1; i < n; i++){j = i-1;int tmp = arr[i];while (j >= 0){if (arr[j] < tmp){arr[j + 1] = arr[j];j--;}else{break;}}arr[j + 1] = tmp;}
}

2、希尔排序

直接插入排序效率不高，在直接插入排序的基础上进行优化，改进，把一个大的集合分为若干个小的集合再进行直接插入排序，从而提升效率。
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

代码实现：

void ShellSort(int* arr, int n)
{int gec = n;int i, j = 0;while (gec > 1){gec = gec / 3 + 1;for (i = gec; i < n; i++){j = i - gec;int tmp = arr[i];while (j >= 0){if (arr[j] < tmp){arr[j + gec] = arr[j];j -= gec;}else{break;}}arr[j + gec] = tmp;}}
}

3、希尔排序时间复杂度分析

外层循环的时间复杂度可以直接给出为： O(log2 n) 或者 O(log3 n) ，即 O(log n)
内层循环：

希尔排序的时间复杂度大约为 ${\log }_2{n}^{1.3}$

三、选择排序

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1、直接选择排序

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int max = begin, min = begin;for (int i = begin + 1; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}if (max == begin){max = min;}{int tmp = a[min];a[min] = a[begin];a[begin] = tmp;}{int tmp = a[max];a[max] = a[end];a[end] = tmp;}begin++;end--;}
}

2、堆排序

void HeapSort(int* arr, int n)
{int i = 0;for (i = (n-1)/2; i>=0; i--){int parent = i;int child = parent * 2 + 1;while (child <= i){if (child + 1 <= i && arr[child + 1] < arr[child]){child++;}if (arr[child] < arr[parent]){int tmp = arr[parent];arr[parent] = arr[child];arr[child] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}}for (i = n - 1; i > 0; i--){int child = i;int parent = 0;int tmp = arr[parent];arr[parent] = arr[child];arr[child] = tmp;child = parent * 2 + 1;while (child < i){if (child + 1 < i && arr[child + 1] < arr[child]){child++;}if (arr[child] < arr[parent]){tmp = arr[parent];arr[parent] = arr[child];arr[child] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}}
}

堆排序的时间复杂度为n$\log n$

四、交换排序

1、冒泡排序

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int falg = 1;for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;falg = 0;}}if (falg){break;}}
}

2、快速排序

通过找基准值，基准值的位置就是这个值该待的位置，然后递归找基准值左边区间和右区间，直到区间不成立位置，确定每个值该待的位置完成排序。

int _QuickSort(int* a, int left, int right)
{int keyi = left;left++;while (left <= right){while (left <= right && a[left] < a[keyi]){left++;}while (left <= right && a[right] > a[keyi]){right--;}if (left <= right){int tmp = a[left];a[left] = a[right];a[right] = tmp;left++;right--;}}int tmp = a[keyi];a[keyi] = a[right];a[right] = tmp;return right;
}void QuickSort(int* a, int left,int right)
{if (left >= right){return;}int keyi = _QuickSort(a, left, right);QuickSort(a, keyi + 1, right);QuickSort(a, left, keyi - 1);}

快排的空间复杂度：O($longn$)
快排的时间复杂度：O(n$longn$)

3、快速排序hoare找基准值

 //快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int keyi = left;++left;while (left < right){while (left <=right && a[right] > a[keyi]){right--;}while (left <= right && a[left] < a[keyi]){left++;}if (left < right){swap(&a[left], &a[right]);}}swap(&a[keyi], &a[right]);return right;
}

4、快排挖坑法找基准值

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int hole = left;int tmp = a[hole];while (left < right){while (left < right && a[right] > tmp){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] < tmp){left++;}a[hole] = a[left];hole = left;}a[hole] = tmp;return hole;
}

5、前后指针法

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int pfast = left + 1;int pslow = left;int keyi = left;while (pfast <= right){while (pfast <= right && a[pfast] < a[keyi] && ++pslow != pfast){swap(&a[pslow], &a[pfast]);}pfast++;}swap(&a[pslow], &a[keyi]);return pslow;
}

6、快速排序非递归实现

// 快速排序 非递归实现//运用栈数据结构
typedef int StackDataType;typedef struct Stack
{int* a;int capacity;int top;
}ST;//栈初始化
void STInit(ST* ps)
{ps->a = NULL;ps->capacity = ps->top = 0;
}//入栈
void STPush(ST* ps,StackDataType x){if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;int* tmp = (int*)realloc(ps->a, newcapacity * sizeof(StackDataType));if (tmp == NULL){perror("realloc fail");return;}ps->capacity = newcapacity;ps->a = tmp;tmp = NULL;}ps->a[ps->top++] = x;
}//判断栈是否为空
bool STEmpty(ST* ps)
{return ps->top == 0;
}//出栈
void STPop(ST* ps)
{if (ps->top == 0){return;}ps->top--;
}//取栈顶元素
StackDataType STTop(ST* ps)
{if (ps->top == 0){exit(1);}return ps->a[ps->top - 1];
}void QuickSortNonR(int* a, int left, int right)
{ST s;STInit(&s);STPush(&s, right);STPush(&s, left);while (!STEmpty(&s)){int begin = STTop(&s);STPop(&s);int end = STTop(&s);STPop(&s);int pfast = begin + 1;int pslow = begin;int keyi = begin;while (pfast <= end){while (pfast <= end && a[pfast] < a[keyi] && ++pslow != pfast){swap(&a[pslow], &a[pfast]);}pfast++;}swap(&a[pslow], &a[keyi]);if (pslow + 1 < end){STPush(&s, end);STPush(&s, pslow + 1);}if (pslow - 1 > begin){STPush(&s, pslow - 1);STPush(&s, begin);}}

五、归并排序

归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（DivideandConquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。

1、递归实现

代码实现：

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (right - left) / 2 + left;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right,tmp);//合并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int begin = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[begin++] = arr[begin1++];}else{tmp[begin++] = arr[begin2++];}}while (begin1 <= end1){tmp[begin++] = arr[begin1++];}while (begin2 <= end2){tmp[begin++] = arr[begin2++];}//传值while (left <= right){arr[left] = tmp[left];left++;}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

2、非递归实现

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(1);}int k = 1;while (k < n){int i = 0;for (i = 0; i < n - 2 * k + 1;i += 2*k){int mid = i + k - 1;int left = i;int right = i + 2 * k - 1;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int begin = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[begin++] = a[begin1++];}else{tmp[begin++] = a[begin2++];}}while (begin1 <= end1){tmp[begin++] = a[begin1++];}while (begin2 <= end2){tmp[begin++] = a[begin2++];}while (left <= right){a[left] = tmp[left];left++;}}if (i < n-k){int mid = i+k-1;int left = i;int right = n-1;int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int begin = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[begin++] = a[begin1++];}else{tmp[begin++] = a[begin2++];}}while (begin1 <= end1){tmp[begin++] = a[begin1++];}while (begin2 <= end2){tmp[begin++] = a[begin2++];}while (left <= right){a[left] = tmp[left];left++;}}k *= 2;}free(tmp);
}

六、排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

七、计数排序

只能排序整数，不适合排不集中的数据如1,10000000,100000002；会产生空间浪费

// 计数排序
void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (min > a[i]){min = a[i];}if (max < a[i]){max = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range ,sizeof(int));for (int i = 0; i < n; i++){count[a[i]-min]++;}int indext = 0;for (int i = 0; i < range; i++){while (count[i]--){a[indext++] = i + min;}}free(count);count = NULL;
}