挖洞法
思路： 创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新 的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结 束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
代码如下：
int _QuickSort(int* arr, int left, int right)
{//定义坑int hole = left;int key = arr[hole];while (left < right){//挖坑while (left<right && arr[right]>arr[key]){--right;}//填坑arr[hole] = arr[left];hole = left;while (left<right&&arr[left]<arr[key]){++left;}arr[hole] = arr[right];hole = right;}arr[hole] = key;return hole;
}
lomuto前后指针
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
int _QuickSort(int* arr, int left, int right)
{//prev起到占位置的作用，cur跟keyi比较大小，找到小于keyi的并且cur!=keyi的时候与//prev交换int prev = left, cur = prev + 1;int keyi = left;while (cur <= right)//这里加不加等号区别不是很大，因为快速排序对于处理这样重复的数据时间复杂度较高{if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}//keyi和prev交换Swap(&arr[keyi], &arr[prev]);return prev;
}
快速排序特性总结：
时间复杂度： O(nlogn)
空间复杂度： O(logn)
快速排序的非递归
需要借助数据结构：栈
代码如下：
//Stack.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity; //栈的空间大小int top; //栈顶
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);//栈顶---入数据、出数据
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);bool StackEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
//Stack.c
#include"Stack.h"void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}void STDestroy(ST* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//QuickSort.h
#include <stdio.h>
void QuickSortNonR(int* arr, int left, int right);
void Swap(int* x, int* y);
//QuickSort.c
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取栈顶元素---取两个int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//类似于双指针法int prev = begin;int cur = prev + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//划分左右区间//右区间if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}//左区间if (keyi - 1 > begin){StackPush(&st, begin);StackPush(&st, keyi - 1);}}
}
归并排序
归并排序算法思想： 归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个 ⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核 ⼼步骤：
//MergeSort.h
#include <stdio.h>
#include <stdlib.h>void MergeSort(int* arr, int n);
void _MergeSort(int* arr, int left, int right, int* tmp);
//MergeSort.c
#include "MergeSort.h"void _MergeSort(int* arr, int left, int right, int* tmp)
{//递归if (left <= right){return;}//基准值int mid = (left + right) / 2;_MergeSort(arr, left, mid - 1, tmp);_MergeSort(arr, mid + 1, right, tmp);//划分左右区间int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;//对于临时数组的初始化，如果是右边的区间，不能够从0开始//合并int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (begin1 <= end1){tmp[index++] = arr[begin1++];}if (begin2 <= end2){tmp[index++] = arr[begin2++];}}//出现越界，要么左区间，要么右区间while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//将临时的拷贝到数组中去for (int i = left; i < right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1,tmp);free(tmp);
}
哈哈哈哈哈还是比较烧脑的，希望大家有所收获,peace!!!
