目录
一，排序种类
1.直接插入排序
2.冒泡排序
3.希尔排序
4.快排
（1.）快排单趟排序三种写法
【1】hoare版本单趟排序
【2】挖坑法
【3】前后指针法 最新的写法，写起来最简单，最不容易出错
(2.)快排
【1.】快排递归
【2】快排非递归
【3】快排的优化一三数取中优化
【4】快排的优化二小区间优化
5.归并排序
（1.）归并排序递归写法
【1】归并排序子函数
【2】归并排序
（2.）归并排序循环写法
6.选择排序
7.堆排序
【1.】向下调整算法
【2.堆排序】
8.计数排序
三，测试排序
【1.】是否排好序
【2.各个排序效率如何呢】
四，代码链接，嘿嘿嘿
一，排序种类
1.直接插入排序
2.冒泡排序
3.希尔排序
4.快排
5.归并排序
6.选择排序
7.堆排序
8.计数排序
void InSertSort(int* a, int n)
{
//但趟排序 [0.end]有序，end+1插入进去、、、
//假设排升序：
//这里i最大取到倒数第二个位置就可以了。把最后一个位置在插入进去就排完了。
for (int i = 0; i < n - 1; i++)
{
//单趟排序 [0,end] 有序，end+1，插入进前面的区间。
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
// 要降序改一下这里符号。
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
//a[end + 1] = tmp; 这句代码这里可以不写，和极端情况进行合并了。
break;
}
}
//极端情况end==-1时。
a[end + 1] = tmp;
}
}2.冒泡排序
/ 最坏：O（N^2）
// 最好：O(N)
//冒泡排序
void BubbleSort(int* a, int n)
{
//假设排升序
for (int j = 0; j < n; j++)
{
int exchenge = 0;
//单趟 多趟加一个j去控制单趟循环的结束位置。
for (int i = 1; i < n-j; i++)
{
if (a[i - 1] > a[i])
{
exchenge = 1;
swap(&a[i - 1],&a[i]);
}
}
//没有发生交换，那么就一定已经有序了，不用在继续冒泡了。
if (exchenge == 0)
break;
}
}3.希尔排序
//希尔排序 算是插入排序的优化
// 平均 O(N^1.3)
// 最坏：O(log3(N) * N) 这里log3(N)是以3为底N的对数
void ShellSort(int* a, int n)
{
//这是一组一组排序的写法，
//
//int gap =n; //这里gap等于3是不肯拍好的，gap大于1时都是预排序的，使之接近有序。再来一个循环控制gap的变化。
//while(gap>1) //gap>1 之前都是预排序的。
//{
// gap=gap/3+ 1; //+1时为了保证gap会有等于1的时候。
控制多个分组的end 位置
// for (int j = 0; j < gap; j++)
// {
// //一个分组的排序 ，控制一个分组end的位置。
// for (int i = j; i < n - gap; i += gap)
// {
// //单趟
// int end = i;
// //[0，end] end加一插入进去
// int tmp = a[end + gap];
// while (end >= 0)
// {
// if (tmp < a[end])
// {
// a[end + gap] = a[end];
// end -= gap;
// }
// else
// {
// //a[end + gap] = tmp; 可以归到特殊情况里面。
// break;
// }
// }
// a[end + gap] = tmp;
// }
// }
//}
//其实我们不需要一组全部排完再去排下一组，可以每组排一个，在每组排一个。
//思想上与前面那种写法是一样的，时间复杂度也是一样的。
int gap =n;
while (gap > 1)
{
gap = gap / 3 + 1;
//一个分组的排序 ，控制一个分组end的位置。
for (int i = 0; i < n - gap; i++)
{
//单趟
int end = i;
//[0，end] end加一插入进去
int tmp = a[end + gap];
while (end >= 0) //end等于01也要比较一次的，万一tmp是最小的呢。
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}4.快排 （1.）快排单趟排序三种写法
效率上没有区别的，写法上，越往后越是新的写的，越好写，越不容易出错。
【1】hoare版本单趟排序int PartSort1(int* a, int left, int right)
{
//三数取中优化
int mid = Getmidindex(a, left, right);
swap(&a[mid], &a[left]);
//假设排升序
int key = left;
//key左边的值比他小，key右边的值比他大，等于key的值，放在左边还是右边都是可以的。
while (left < right)
{
//右边先走，右边找小。
while (left < right && a[right] >= a[key])
right--;
//左边后走，左边找大。
while(left < right && a[left] <= a[key])
left++;
swap(&a[left], &a[right]);
}
//1.因为右边先走的，所以相遇点一定是小于a[key],
//2.或者右边直接找到了left也就是a[key]，那这时左边不能找了，自己与自己交换下也没啥。
swap(&a[left], &a[key]);
//left 是最后相遇点
return left;
}int PartSort2(int* a, int left, int right)
{
//三数取中优化
int mid = Getmidindex(a, left, right);
swap(&a[mid], &a[left]);
//不需要考虑left=key)
right--;
a[pit] = a[right];
pit = right; //更新坑位。
while (left < right && a[left] <=key)
left++;
a[pit] = a[left];
pit = left;
}
a[pit]=key;
return pit;
} int PartSort3(int* a, int left, int right)
{
//三数取中优化
int mid = Getmidindex(a, left, right);
swap(&a[mid], &a[left]);
//左边做key
int prev = left; //left左key
int cur = left + 1;
int keyi=left;
while (cur <=right) //==也要进行一次比较的。
{
//prev及prev之前的都是小于key的,之后都是大于key的。
while (a[cur] < a[keyi] && ++prev != cur) // 防止自己和自己交换 a[prev+1]!=a[cur] 这样用值比较还行也许，
//但是用值判断是不是自己，感觉不太好.
swap(&a[cur], &a[prev]); //再这里++prev是不对的。
cur++;//跳过大于key的，继续向后找小于key的。
}
swap(&a[keyi], &a[prev]);
return prev;
//右边做key
//int prev = left-1;
//int cur = left;
//int keyi = right;
//while (cur void QuickSort(int* a, int begin,int end)
{
//等于是区间只有一个数据，已经在他该在的位置了。
//还有一种是区间是不和法的，分过了，直接返回就好了。
if (begin >= end)
return;
int keyi = PartSort3(a, begin, end);
//分治为子问题，递归去解决。 按照区间划分。[begin,keyi-1] keyi [keyi+1,end];
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1,end);
}这里其实是用我们之前写的 栈去模拟递归的，如果之前没有写的话，c++里面stl是直接有的，但是c语言没有，需要去写一下栈就好了。
void QuickSort2(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi = PartSort3(a, left, right);
//[begin,keyi-1] [keyi+1,end]
if (left < keyi - 1)
{
StackPush(&st,left);
StackPush(&st, keyi - 1);
}
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
}
StackDestory(&st);
}这个是快排的核心优化，非常重要
//三数取中
int Getmidindex(int* a, int left, int right)
{
int mid = left+(right - left) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
return right;
else
{
if (a[left] < a[right])
return left;
else
return right;
}
}
else
{
if (a[mid] < a[right])
return mid;
else
{
if (a[left] > a[right])
return left;
else
return right;
}
}
/*if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else
{
if (a[left] > a[right])
return left;
else
return right;
}
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[left] < a[right])
return left;
else
return right;
}*/
}
这个优化堆快排的效率优化不是特别大，但是也是有优化的。
//快排的小区间优化， 也就是当区级比较小时，不去递归再分了，改用插入排序去直接排好序。
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
return;
if (end-begin+1 <=20)
{
//注意这里一定要注意的是 a+begin 才是起点。 后面是end-begin，小心写反了。
InSertSort(a+begin, end-begin + 1);
}
else
{
int keyi = PartSort3(a, begin, end);
QuickSort1(a, begin, keyi-1);
QuickSort1(a, keyi+1,end);
}
}因为用子函数更方便一点，我们写一个子函数去递归
//归并子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
//只有一个或者区间不存在。
if (begin >= end)
return;
int mid = begin + (end - begin) / 2;
//[begin,mid] [mid+1,end]
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
//但是要注意这样子划分区间是不行的 [begin,mid-1] [mid,end]
//因为如果遇到奇数偶数子再一起的，相除是奇数，第一个区间不存在，但是第二个区间不会往前走，死循环了就。
_MergeSort(a, begin1, end1, tmp);
_MergeSort(a, begin2, end2, tmp);
//走到这里的话，那就说明这里的左右是有序的了，进行归并
//也就是[begin1,end1] [begin2,end2] 区间有序了。
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//剩下的再放在后面。
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//归并好的那一段拷贝回原数组，注意不是从开始拷贝的。
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");
}
_MergeSort(a,0,n-1,tmp);
free(tmp);
}用循环写是因为优先情况下递归太深回造成栈溢出的，所以用循环去该
//递归 现代编译器优化很好，性能已经不是大问题
//最大的问题->递归深度太深，程序本身没问题，但是栈空间不够，导致栈溢出
//只能改成非递归，改成非递归有两种方式：
//1、直接改循环-》斐波那契数列求解
//2、树遍历非递归和快排非递归等等，只能用Stack存储数据模拟递归过程
//归并排序循环写法
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp== NULL)
{
printf("malloc fail\n");
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// 注意边界控制，带几个值取看看。
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//修正1 思路简单。
//if (end1 >= n)
// end1 = n - 1;
//if (begin2>=n)
//{
// begin2 = n;
// end2 = n - 1;
//}
//if (begin2 < n && end2 >= n)
//{
// end2 = n - 1;
//}
//修正2
//注意最后一次归并特殊情况（越界代码就会****崩****，再free（）的时候，就会报错） 1.3.归为一种情况，第二个区间不存在就不用再归了。
//1.最后一个小组归并时，第二个小区间不存在，不需要归并了。
//2.最后一个小组归并时，第二个小区间存在，但是第二个小区间不够gap个。
//3.最后一个小组归并时，第一个小区间不够gap的，不需要归并了。
//
// 如果第二个小区间不存在就 ***不需要归并了***，结束本次循环
if (begin2 >= n) // 1.3的情况，第一个满，begin2等于n，第一个都不满，begin2大于n。
break;
//走到这里的话那就是begin2是小于n的，并且第一个区间存在。
// 如果第二个小区间存在，但是第二个小区间不够gap个，结束位置越界了，需要修正一下
if (end2 >= n)
end2 = n - 1; //直接修正到数组最后一个值的位置。
//用来打印区别看是否正确，比较是方便一点
//然后就可以用条件断点直接跳到错误的地方低调试。
//然后后我们发现其实区间越界了，需要我们取修正。
//printf("[%d %d][%d %d]\n", begin1, end1, begin2, end2);
//条件断点，方便调试
//if (begin1 == 12 && end1 == 13 && begin2 == 14 && end2 == 15)
//{
// int x = 0;
// int y = 0;
//}
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++]= a[begin2++];
}
}
//剩下没有归完的，继续归。
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
}
//拷贝回原数组，一个gap全部归完再去拷贝。
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
}6.选择排序
//选择排序
void SelectSort(int* a, int n)
{
//写一个优化一点的版本，俩边找一个最大，最小。
int left = 0;
int right = n - 1;
while (left < right)
{
int maxi = left, mini = left;
for (int i = left; i <= right; i++) //i==right也是要比较的。这里right和left都是闭区间。
{
//找最大值
if (a[maxi] < a[i])
maxi = i;
//找最小值
if(a[mini] > a[i])
mini =i;
}
swap(&a[mini], &a[left]);
if (maxi == left)
{
//此时要进行修正最大值，因为最大值已经被换到mini坐标的位置上去了。
maxi = mini;
}
swap(&a[maxi], &a[right]);
left++;
right--;
}
}7.堆排序 【1.】向下调整算法
//向下调整算法， 假设这里我们要建大堆 为了排升序
void AdjustDown(int* a,int size,int root)
{
int parent = root;
int child = parent*2+1; //左孩子
while (childa[child])
child++;
if (a[child]>a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break; //已经是小堆了，不需要再调整了。
}
}
} //O(N*log(N)
// 堆排序
void HeapSort(int* a, int n)
{
int index= (n - 2) / 2; //最后一个孩子的父亲。
//建堆 假设升序，建大堆
for (int i = index; i>=0; i--)
{
AdjustDown(a, n, i);
}
int j = 0;
for (int i = n-1; i>0; i--)
{
swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
}8.计数排序
时间复杂度：O(N+range)
只适合，一组数据，数据的***范围比较集中***8. 如果范围集中，效率是很高的，但是局限性也在这里
并且只适合整数，如果是浮点数、字符串等等就不行了
空间辅助度：O(range)
// 计数排序
void CountSort(int* a, int n)
{
//求出最大，最小数
int max = a[0], min = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
//求有出几个数
int range = max - min + 1;
int* count = malloc(sizeof(int) * range);
//初始化数组：
memset(count, 0, sizeof(int) * range);
//这里使用相对映射记数，节省空间。
for (int i = 0; i < n; ++i)
{
count[a[i] - min]++;
}
int i = 0;
for (int j = 0; j < range; ++j)
{
while (count[j]--) //后置--，是几就进行几次
{
a[i++] = j + min; //相对映射
}
}
free(count);
}//void InSertSort() 这样子取名字会被误认为函数定义的，那么就重定义了。
void testInSertSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
InSertSort(a, sizeof(a) / sizeof(a[0]));
printf("InSertSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testBubbleSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
BubbleSort(a, sizeof(a) / sizeof(a[0]));
printf("BubbleSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testHeapSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
HeapSort(a, sizeof(a) / sizeof(a[0]));
printf("HeapSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testShellSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
ShellSort(a, sizeof(a) / sizeof(a[0]));
printf("ShellSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort1()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
QuickSort(a, 0,sizeof(a) / sizeof(a[0])-1);
printf("QuickSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort2()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
printf("QuickSort1\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort3()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
QuickSort2(a, 0, sizeof(a) / sizeof(a[0]) - 1);
printf("QuickSort2\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testSelectSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
SelectSort(a,sizeof(a) / sizeof(a[0]));
printf("SelectSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testMergeSort()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
MergeSort(a, sizeof(a) / sizeof(a[0]));
printf("MergeSort\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}
void testMergeSortNonR()
{
int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
//按照闭区间写的。
MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
printf("MergeSortNonR\n");
Printf(a, sizeof(a) / sizeof(a[0]));
}是骡子是马，拉出来溜溜
测试代码
void TestOP()
{
srand(time(0));
const int N = 1000000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int) * N);
int* a9 = (int*)malloc(sizeof(int) * N);
int* a10 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
a9[i] = a1[i];
a10[i] = a1[i];
}
int begin1 = clock();
//InSertSort(a1, N);
int end1 = clock();
int begin2 = clock();
//ShellSort(a2, N);
int end2 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = clock();
int begin3 = clock();
//SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
//HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
QuickSort1(a6, 0, N - 1);
int end6 = clock();
int begin8 = clock();
QuickSort2(a8, 0, N - 1);
int end8 = clock();
int begin9 = clock();
MergeSortNonR(a9,N);
int end9 = clock();
int begin10= clock();
MergeSortNonR(a10, N);
int end10= clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("BublleSort:%d\n", end7 - begin7);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("QuickSort1:%d\n", end6 - begin6);
printf("QuickSort2:%d\n", end8 - begin8);
printf("MergeSortNonR:%d\n", end9 - begin9);
printf("MergeSort:%d\n", end10 - begin10);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
testInSertSort();
testBubbleSort();
testShellSort();
testQuickSort1();
testQuickSort2();
testQuickSort3();
testSelectSort();
testHeapSort();
testMergeSort();
testMergeSortNonR();
TestOP();
return 0;
}data structure: 数据解构练习 - Gitee.com
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）