【数据结构】排序代码分享

Stack.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>//静态栈
/*
#define N 10
typedef int STDataType;
typedef struct Stack
{STDataType a[N];int top;
}ST;
*/typedef int STDataType;
typedef struct Stack
{int top;      //栈顶位置int capacity;STDataType* a;
}ST;//初始化
void StackInit(ST* ps);//销毁
void StackDestroy(ST* ps);//压栈
void StackPush(ST* ps, STDataType x);//出栈
void StackPop(ST* ps);//栈顶数据
STDataType StackTop(ST* ps);//判空
bool StackEmpty(ST* ps);//栈大小
int StackSize(ST* ps);

Stack.c

#include "Stack.h"//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}//销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//压栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}//取栈顶
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}//判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//栈大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

Sort.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>//打印函数
void PrintArray(int* a, int n);//插入排序
void InsertSort(int* a, int n);//希尔排序
void ShellSort(int* a, int n);//选择排序
void SelectSort(int* a, int n);//堆排序
void HeapSort(int* a, int n);//冒泡排序
void BubbleSort(int* a, int n);//快速排序
extern int count;        //测试快排递归次数
void QuickSort(int* a, int begin, int end);
void QuickSort_NonRecursion(int* a, int begin, int end);//归并排序
void MergeSort(int* a, int n);
void MergeSort_NonRecursion1(int* a, int n);
void MergeSort_NonRecursion2(int* a, int n);//计数排序
void CountSort(int* a, int n);

Sort.c

#include "Sort.h"
#include "Stack.h"// 打印函数
void PrintArray(int *a, int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}// 插入排序 0 ~ n-2   O(num) ~ O(num^2)
// 数据越接近有序 插入排序效率越高
void InsertSort(int *a, int n)
{int i, j, t;for (i = 0; i < n - 1; i++){t = a[i + 1];for (j = i; j >= 0 && t < a[j]; j--)a[j + 1] = a[j];if (j != i)a[j + 1] = t;}
}// 希尔排序
void ShellSort(int *a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;int i, j, t;for (i = 0; i < n - gap; ++i){t = a[i + gap];for (j = i; j >= 0 && t < a[j]; j -= gap){a[j + gap] = a[j];}if (j != i)a[j + gap] = t;}}
}void Swap(int *a, int *b)
{if (*a == *b)return;else{int t = *a;*a = *b;*b = t;}
}// 选择排序：O(num^2) ~ O(num^2)
void SelectSort(int *a, int n)
{assert(a);// i：数据头 j：数据尾for (int i = 0, j = n - 1; i < j; ++i, --j){// 假设最大值/最小值下标为iint m = i, M = i;// 遍历i后到j的所有数据 确定real_m/Mfor (int k = i + 1; k <= j; ++k){if (a[k] < a[m])m = k;if (a[k] > a[M])M = k;}// 小值换到数据头Swap(&a[i], &a[m]);// 特殊情况: 原M即数据头即为max 经过第一次Swap后max和min换位// 此时要把M重定位if (i == M){M = m;}// 大值换到数据尾Swap(&a[j], &a[M]);}
}// 下调/筛选法建堆 O(N)  上调建堆O(NlogN)
// 升序建大堆--循环把大堆头放到尾部
void AdjustDwon(int *a, int size, int parent)
{// 设左孩子较小int child = parent * 2 + 1;// 当未达到堆末 进入循环while (child < size){// 确定real小孩子// if (child + 1 < size && a[child + 1] < a[child])  //小堆// 确定real大孩子if (child + 1 < size && a[child + 1] > a[child]) // 大堆{++child;}// if (a[parent] > a[child])    //小堆if (a[parent] < a[child]) // 大堆{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int *a, int n)
{// 下调建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDwon(a, n, i);}// 排序int end = n - 1; // 此时end表示堆尾数据的下标while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0); // 此时end表示传过去数据个数(n-1)--end;}
}// 插入排序  O(num)~O(num^2)
// 冒泡排序  O(num)~O(num^2)
// 当数据有序 二者均为O(num) 当数据接近有序或局部有序 插排更优
void BubbleSort(int *a, int n)
{assert(a);int flag = 1;// n-1轮for (int i = 0; flag && i < n - 1; ++i){flag = 0;// 首轮n-1次 依次递减for (int j = 0; j < n - 1 - i; ++j){if (a[j] > a[j + 1]){Swap(&a[j + 1], &a[j]);flag = 1;}}}
}// 快速排序   O(num * logN)
int count = 0; // 测试递归次数
// 对任意区间抽三值取中位数
int GetMid_X(int *a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end])return mid;else if (a[end] < a[begin])return begin;elsereturn end;}else // a[begin] >= a[mid]{if (a[mid] > a[end])return mid;else if (a[end] > a[begin])return begin;elsereturn end;}
}// 霍尔版本 右找小 左找打 大小交换 依次递归
int PartQuickSort1(int *a, int begin, int end)
{int x = begin;int left = begin, right = end;// 确定更合适的keyint mid_x = GetMid_X(a, begin, end);Swap(&a[x], &a[mid_x]);while (left < right){// 右找小while (left < right && a[right] >= a[x])--right;// 左找大while (left < right && a[left] <= a[x])++left;Swap(&a[left], &a[right]);}Swap(&a[x], &a[left]);x = left;return x;
}// 挖坑版本/教学版本 记录a[x]=key x位假想无效/置空
// 右找小入坑 坑位更新 左找大入坑 坑位更新 依次递归
int PartQuickSort2(int *a, int begin, int end)
{int x = begin;// 确定更合适的keyint mid_x = GetMid_X(a, begin, end);Swap(&a[x], &a[mid_x]);int key = a[x];while (begin < end){while (begin < end && a[end] >= key)--end;a[x] = a[end];x = end;while (begin < end && a[begin] <= key)++begin;a[x] = a[begin];x = begin;}a[x] = key;return x;
}// 指针版本
int PartQuickSort3(int *a, int begin, int end)
{int x = begin;int prv = begin, cur = begin + 1;// 确定更合适的keyint mid_x = GetMid_X(a, begin, end);Swap(&a[x], &a[mid_x]);while (cur <= end){if (a[cur] < a[x] && ++prv != cur)Swap(&a[prv], &a[cur]);++cur;}Swap(&a[prv], &a[x]);x = prv;return x;
}void QuickSort(int *a, int begin, int end)
{count++;if (begin >= end)return;if (end - begin > 10){int x = PartQuickSort3(a, begin, end);QuickSort(a, begin, x - 1);QuickSort(a, x + 1, end);}elseInsertSort(a + begin, end - begin + 1);
}// 非递归版本
void QuickSort_NonRecursion(int *a, int begin, int end)
{ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);int x = PartQuickSort3(a, begin, end);if (x + 1 < end){StackPush(&st, x + 1);StackPush(&st, end);}// [begin, x-1] x [x+1, end]if (begin < x - 1){StackPush(&st, begin);StackPush(&st, x - 1);}}StackDestroy(&st);
}//归并排序 时间复杂度：O(N*logN)   空间复杂度：O(N)
void PartMergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;//[begin, mid] [mid+1, end] PartMergeSort(a, begin, mid, tmp);PartMergeSort(a, mid + 1, end, tmp);// [begin, mid] [mid+1, end]//   [i, mid]    [j, end]int i = begin, j = mid + 1, k = i;while (i <= mid && j <= end){if (a[i] < a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}while (i <= mid)tmp[k++] = a[i++];while (j <= end)tmp[k++] = a[j++]; memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}//void PartMergeSort(int* a, int begin, int end, int* tmp);PartMergeSort(a, 0, n - 1, tmp);free(tmp);
}void MergeSort_NonRecursion1(int *a, int n)
{int *tmp = (int *)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}int range = 1;while (range < n){//printf("num = %d ->", range);for (int index = 0; index < n; index += 2 * range){int i = index, k = i, end = index + range - 1;int j = index + range, End = index + 2 * range - 1;// 修正边界if (end >= n){end = n - 1;j = n;End = n - 1;}else if (j >= n){j = n;End = n - 1;}else if (End >= n)End = n - 1;//printf("[%d,%d]--[%d, %d]  ", i, end, j, End);// 数据排序while (i <= end && j <= End){if (a[i] <= a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}while (i <= end)tmp[k++] = a[i++];while (j <= End)tmp[k++] = a[j++];}//printf("\n");memcpy(a, tmp, sizeof(int) * n);range *= 2;}free(tmp);
}
void MergeSort_NonRecursion2(int *a, int n)
{int *tmp = (int *)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}int range = 1;while (range < n){//printf("num=%d->", range);for (int index = 0; index < n; index += 2 * range){int i = index, k = i, end = index + range - 1;int j = index + range, End = index + 2 * range - 1;if (end >= n || j >= n)break;else if (End >= n)End = n - 1;//printf("[%d,%d]--[%d,%d]  ", i, end, j, End);int m = End - i + 1;while (i <= end && j <= End){if (a[i] <= a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}while (i <= end)tmp[k++] = a[i++];while (j <= End)tmp[k++] = a[j++];memcpy(a + index, tmp + index, sizeof(int) * m);}//printf("\n");range *= 2;}free(tmp);
}// 计数排序  时间复杂度：O(max(num, N)) 空间复杂度：O(num）
void CountSort(int *a, int n)
{// 确定最值int min = a[0], max = a[0];for (int i = 1; i < n; ++i){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int num = max - min + 1; // 最多有N个"连续"的数据// 开空间int *arr = (int *)malloc(sizeof(int) * num);if (arr == NULL){printf("malloc fail\n");exit(-1);}memset(arr, 0, sizeof(int) * num);// a的数据映射到arr的下标 arr的值存储对应数据出现次数for (int i = 0; i < n; ++i)arr[a[i] - min]++;for (int i = 0, j = 0; i < num; ++i){while (arr[i]--)a[j++] = i + min;}
}

main.cc

#include <iostream>
#include "Sort.h"
using namespace std;int main()
{// 测试各个排序算法int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};int n = sizeof(a) / sizeof(int);InsertSort(a, n);cout << " 插入排序：";PrintArray(a, n);ShellSort(a, n);cout << " 希尔排序：";PrintArray(a, n);SelectSort(a, n);cout << " 选择排序：";PrintArray(a, n);HeapSort(a, n);cout << " 堆排序：  ";PrintArray(a, n);BubbleSort(a, n);cout << " 冒泡排序：";PrintArray(a, n);QuickSort(a, 0, n - 1);cout << " 快速排序：";PrintArray(a, n);QuickSort_NonRecursion(a, 0, n - 1);cout << "非递归快： ";PrintArray(a, n);MergeSort(a, n);cout << " 归并排序：";PrintArray(a, n);MergeSort_NonRecursion1(a, n);cout << "非递归并： ";PrintArray(a, n);MergeSort_NonRecursion2(a, n);cout << "非递归并： ";PrintArray(a, n);CountSort(a, n);cout << " 计数排序：";PrintArray(a, n);return 0;
}