腾讯云10g数字盘做网站够么,网站法人与负责人,做红木家具推广哪个网站比较好,可以自己做漫画的网站文章目录 前言一、常见排序算法的实现1.插入排序1.直接插入排序2.希尔排序 2.交换排序1.冒泡排序2.快速排序1.hoare版2.挖坑版3.前后指针版4.改进版5.非递归版 3.选择排序1.直接选择排序2.堆排序 4.归并排序1.归并排序递归实现2.归并排序非递归实现 5.计数排序 二、排序算法复杂… 文章目录 前言一、常见排序算法的实现1.插入排序1.直接插入排序2.希尔排序 2.交换排序1.冒泡排序2.快速排序1.hoare版2.挖坑版3.前后指针版4.改进版5.非递归版 3.选择排序1.直接选择排序2.堆排序 4.归并排序1.归并排序递归实现2.归并排序非递归实现 5.计数排序 二、排序算法复杂度及稳定性排序测试 前言
所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。排序在我们生活中非常常见比如买东西看的销量价格的对比等。排序也分为内部排序和外部排序。内部排序是数据元素全部放在内存中的排序外部排序则是数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。下面让我们正式认识排序吧。
一、常见排序算法的实现
1.插入排序
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。
1.直接插入排序
void InsertSort(int* nums, int numsSize)
{int i 0;//i变量控制的是整个比较元素的数量for (i 0; i numsSize; i){int num nums[i];//从后面一次和前面的元素进行比较前面的元素大于后面的数据则前面的元素向后移动int j i - 1;while (j -1){if (nums[j] num){//要交换的元素小于前一个元素nums[j 1] nums[j];j--;}else{break;}}//把该元素填到正确的位置nums[j 1] num;}
}测试用例
void sortArray(int* nums, int numsSize)
{InsertSort(nums, numsSize);//插入排序
}
void print(int* nums, int numsSize)
{int i 0;for (i 0; i numsSize; i){printf(%d , nums[i]);}
}
int main()
{int nums[] { 3,9,0,-2,1 };int numsSize sizeof(nums) / sizeof(nums[0]);//计算数组大小sortArray(nums, numsSize);//调用排序算法print(nums, numsSize);//打印排序结果return 0;
}直接插入排序的优点元素集合越接近有序直接插入排序算法的时间效率越高。 时间复杂度ON ^2 空间复杂度O1 直接插入排序是一种稳定的排序算法。
2.希尔排序
将待排序的序列分成若干个子序列对每个子序列进行插入排序使得整个序列基本有序然后再对整个序列进行插入排序。是插入排序的改进
void ShellSort(int* nums, int numsSize)
{int group numsSize;while (group 1){//进行分组//加1为了保证最后一次分组为1组后一次必须要进行正常的插入排序group group / 3 1;int i 0;//每次对分的组进行排序//和插入排序思路相同for (i 0; i numsSize; i){int num nums[i];int j i - group;while (j 0){if (nums[j] num){nums[j group] nums[j];j - group;}else{break;}}nums[j group] num;}}
}group为1时为插入排序必须要保证最后一次group为1这样排序才能正确。希尔排序法也称缩小增量法 希尔排序是对直接插入排序的优化。 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 当group 1时都是预排序目的是让数组更接近于有序让大的数能更快到达后面小的数可以更快到达前面。当group 1时数组已经接近有序的了这时间使用插入可以让插入排序时间复杂度接近ON。从而达到优化效果。希尔排序的时间复杂度大约为ON^1.3。 测试用例
void sortArray(int* nums, int numsSize)
{//InsertSort(nums, numsSize);//插入排序ShellSort(nums, numsSize);//希尔排序
}
int main()
{int nums[] { 3,9,0,-2,1 };int numsSize sizeof(nums) / sizeof(nums[0]);//计算数组大小sortArray(nums, numsSize);//调用排序算法print(nums, numsSize);//打印排序结果return 0;
}2.交换排序
1.冒泡排序
void BubbleSort(int* nums, int numsSize)
{int i 0;//控制循环次数for (i 0; i numsSize; i){int j 0;//用记录该数组是否有序可以提前退出循环int flag 0;//用来控制比较次数for (j 0; j numsSize - i - 1; j){if (nums[j 1] nums[j]){swap(nums[j], nums[j 1]);flag 1;}}//当该此循环不在进行交换则证明数组已经有序可以提前退出循环if (flag 0){break;}}
}冒泡排序非常容易理解它的时间复杂度为O(N^2) 空间复杂度O(1)且很稳定。
2.快速排序
任取待排序元素序列中的某元素作为标准值按照该排序码将待排序集合分成两段左边中所有元素均小于该值右边中所有元素均大于该值然后左右两边重复该过程直到所有元素都排列在相应位置上为止。
1.hoare版
void PartSort1(int* nums, int left, int right)
{//当区间不存在或者区间只有一个数时结束递归if (left right){return ;}int key left;int begin left;int end right;while (begin end){//右边先走目的是结束是相遇位置一定比key值小//开始找比选定值小的元素while ((begin end) (nums[key] nums[end])){end--;}//开始找比选定值大的元素while ((begin end) (nums[begin] nums[key])){begin;}//把两个数进行交换swap(nums[begin], nums[end]);}//把关键值和相遇点的值进行交换由于右边先走相遇值一定小于关键值swap(nums[key], nums[begin]);key begin;//开始递归左边区间PartSort1(nums, left, key - 1);//开始递归右边区间PartSort1(nums, key 1, right);
}分别递归左右区间直到递归为不可在分割的区间是分治算法每次递归都会有一个数回到正确的位置。
2.挖坑版 void PartSort2(int* nums, int left, int right){if (left right){return;} int hole left;//坑的位置 int key nums[left];//记录初始坑位置的值int begin left;int end right;while (begin end){while ((begin end) (key nums[end])){end--;} nums[hole] nums[end];//把小于初始坑位置的填到坑中hole end;//更新坑的位置while ((begin end) (nums[begin] key)){begin;}nums[hole] nums[begin];//把大于初始坑位置的填到坑中hole begin;//更新坑的位置}//坑的位置放置初始坑位置的值nums[begin] key;//开始递归左边区间PartSort2(nums, left, hole - 1);//开始递归右边区间PartSort2(nums, hole 1, right);}注意要先将第一个数据存起来形成第一个坑位才可以进行覆盖。
3.前后指针版
void PartSort3(int* nums, int left, int right){if (left right){return;}//记录关键值int key nums[left];//快指针为关键值的下一个位置int fast left 1;//慢指针为关键值的位置int slow left;while (fast right){//当快指针的值小于关键值时if (nums[fast] key){//当慢指针的下一个不为快指针时则不进行交换if (slow ! fast){swap(nums[fast], nums[slow]); }}//对快指针进行移动fast;//简写形式//if (nums[fast] key slow ! fast)//{// swap(nums[slow], nums[fast]);//}//fast;}//关键值的位置和慢指针进行交换swap(nums[left], nums[slow]);//开始递归左边区间PartSort3(nums, left, slow - 1);//开始递归右边区间PartSort3(nums, slow 1, right);}4.改进版
当要排序的区间为有序时我们排序就是最坏的情况这时间就需要我们进行优化一下。 我们要加三数取中操作。
//三数取中
void middle(int* nums, int left, int right)
{//找到中间的数交换到数组开头因为我们关键值选则的为数组的左边值int middle (left right) / 2;if (nums[left] nums[middle]){if (nums[middle] nums[right]){swap(nums[left], nums[middle]);}else{swap(nums[left], nums[right]);}}else{if (nums[right] nums[left]){swap(nums[left], nums[right]);}}
}
void QuickSort(int* nums, int left, int right)
{if (left right){return;}middle(nums, left, right);//把中间值换到排序的开始位置int key left;int begin left;int end right;while (begin end){//右边先走目的是结束是相遇位置一定比key值小while ((begin end) (nums[key] nums[end])){end--;}while ((begin end) (nums[begin] nums[key])){begin;}swap(nums[begin], nums[end]);}swap(nums[key], nums[begin]);key begin;QuickSort(nums, left, key - 1);QuickSort(nums, key 1, right);
}我们实现的版本1的改进版本2和3改进同理只是增加一个调用函数。
5.非递归版
当我们拍的数据递归调用太深的情况就会造成栈破坏所以非递归版本的快排也是重中之重。让我们实现一下吧。非递归中我们用到之前学的栈来辅助我们完成。
void QuickSortNonR(int* nums, int left, int right)
{Stack st;//创建栈StackInit(st);//初始话栈StackPush(st, right);//把要排序的右边界入栈这时会先左边界先出栈StackPush(st, left);//把要排序的左边界入栈while (!StackEmpty(st))//如果栈不为空则一直进行循环{int left StackTop(st);//获得要排序的左边界StackPop(st);//把左边界出栈int right StackTop(st);//获得要排序的右边界StackPop(st);//把右边界出栈if (left right)//如果边界不合法则跳过本次循环{continue;}//快速排序版本1int key left;int begin left;int end right;while (begin end){//右边先走目的是结束是相遇位置一定比key值小while ((begin end) (nums[key] nums[end])){end--;}while ((begin end) (nums[begin] nums[key])){begin;}swap(nums[begin], nums[end]);}swap(nums[key], nums[begin]);key begin;StackPush(st, key-1);//把左边界的结束位置入栈StackPush(st, left);//把左边界的起始位置入栈StackPush(st, right);//把右边界的结束位置入栈StackPush(st, key1);//把右边界的起始位置入栈}StackDestroy(st);//销毁栈
}快排在一般情况下效率非常高且可以搭配其他排序进行小区间优化。它的时间复杂度为O(N*logN)空间复杂度为O(logN)但不稳定
3.选择排序
每一次从待排序的数据元素中选出最小或最大的一个值存放在数据的起始位置直到全部待排序的数据元素排完。
1.直接选择排序
void SelectSort(int* nums, int numsSize)
{int i 0;for (i 0; i numsSize; i){int min i;//记录最小数的下标int j 0;for (j i; j numsSize; j)//开始寻找最小数{if (nums[j] nums[min]){min j;//记录下标}}if (min ! i){swap(nums[min], nums[i]);//如果最小数和开始位置不相同则进行交换}}
}直接选择排序非常好理解但是效率太低。实际中很少使用
2.堆排序
堆的思想和树一样。堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法我们升序要建大堆降序要建小堆
void AdjustDwon(int* nums, int n, int root)
{int left root * 2 1;while (left n){if (((left 1) n) (nums[left] nums[left 1]))//当右子树存在并且右子树的值大于左子树{left left 1;//更新节点的下标}if (nums[root] nums[left]){swap(nums[root], nums[left]);//如果根节点小于孩子节点就进行交换root left;//更新根节点left root * 2 1;//更新孩子节点}else//已符合大堆结构跳出循环{break;}}
}
//建大堆
void HeapSort(int* nums, int numsSize)
{int i 0;//从第一个非叶子节点开始进行建堆当左右都为大堆时才会排根节点for (i (numsSize - 1 - 1) / 2; i 0; --i){AdjustDwon(nums, numsSize, i);}while (numsSize--){swap(nums[0], nums[numsSize]);//如果根节点小于孩子节点就进行交换//调整堆结构AdjustDwon(nums, numsSize, 0);}
}堆排序使用堆来选数效率比直接排序高很多。它的时间复杂度为O(N*logN)且空间复杂度为O(1)但是不稳定。
4.归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法。先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表。归并需要一个临时的空间来存放子序列用来拷贝到源序列中
1.归并排序递归实现
void MergeSort(int* nums, int left, int right,int *tmp)
{if (left right){return;}//把区间拆分为两段int middle (left right) 1;//拆分MergeSort(nums, left, middle, tmp);MergeSort(nums, middle1, right, tmp);//归并int begin1 left;int begin2 middle 1;int end1 middle;int end2 right;int i 0;//和链表的链接差不多//直到有一个区间结束结束循环while ((begin1 end1) (begin2 end2)){//那个值小那个值进入开辟的数组if (nums[begin1] nums[begin2]){tmp[i] nums[begin1];}else{tmp[i] nums[begin2];}}//找到未完全结束的数组并且把数组中的元素尾加到开辟的数组中while (begin1 end1){tmp[i] nums[begin1];}while (begin2 end2){tmp[i] nums[begin2];}//把开辟的数组中的内容拷贝到源数组中//拷贝时要注意拷贝时的位置memcpy(nums left, tmp, (right - left 1) * sizeof(int));
}2.归并排序非递归实现
void MergeSortNonR(int* nums, int numsSize, int* tmp)
{//归并所用的数int gap 1;int i 0;while(gap numsSize)//当归并使用的数小于数组大小时进行循环{for (i 0; i numsSize;)//用i来控制归并的位置{int begin1 i;int begin2 i gap;int end1 i gap - 1;int end2 i 2 * gap - 1;//当end1越界时进行修正此时begin2和end2都会越界时进行修正if (end1 numsSize - 1){end1 numsSize - 1;begin2 numsSize 1;end2 numsSize;}//当begin2越界时进行修正此时end2也会越界else if (begin2 numsSize - 1){begin2 numsSize 1;end2 numsSize;}//当end2越界时进行修正else if(end2 numsSize - 1){end2 numsSize - 1;}//开始进行归并while ((begin1 end1) (begin2 end2)){if (nums[begin1] nums[begin2]){tmp[i] nums[begin1];}else{tmp[i] nums[begin2];}}//找到未结束的数组插入到临时数组中while (begin1 end1){tmp[i] nums[begin1];}while (begin2 end2){tmp[i] nums[begin2];}}//把临时数组的内容拷贝到源数组中memcpy(nums, tmp, numsSize * sizeof(int));//把归并的范围扩大gap * 2;}
}归并排序的非递归要注意边界的修正不然会产生越界的情况。 归并的缺点在于需要O(N)的空间但归并排序的思考更多的是解决在磁盘中的外排问题。可以当内排序也可以当外排序使用且时间复杂度为O(N*logN)是一种稳定的排序。
5.计数排序
void CountSort(int* nums, int numsSize)
{int i 0;int min nums[i];int max nums[i];//找到原数组中的最大值和最小值for (i 0; i numsSize; i){if (min nums[i]){min nums[i];}if (max nums[i]){max nums[i];}}//计算出排序中最大和最小值的差加上1为要开辟临时数组的大小int num max - min 1;//创建相应的大小的空间int* tmp (int*)malloc(sizeof(int) * num);//对创建的空间进行初始话把里面的元素全部置0memset(tmp, 0, sizeof(int) * num);//遍历原数组把该元素值的下标映射到临时数组中for (i 0; i numsSize; i){tmp[nums[i] - min];}int j 0;//遍历临时数组把该元素不为0的恢复原值拷贝到原数组中for (i 0; i num; i){while (tmp[i]--){nums[j] i min;}}free(tmp);
}计数排序在数据范围集中时效率很高但是适用范围及场景有限。
二、排序算法复杂度及稳定性
排序方法平均情况最好情况最坏情况空间消耗稳定性直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(N*logN)~O(N^2)O(N^1.3)O(N^2)O(1)不稳定冒泡排序O(N^2)O(N)O(N^2)O(1)稳定快速排序O(N*logN)O(N*logN)O(N^2)O(N*logN)~O(N)不稳定选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定堆排序O(N*logN)O(N*logN)O(N*logN)O(1)不稳定归并排序O(N*logN)O(N*logN)O(N*logN)O(N)稳定
排序测试
int tmp1[20];
int tmp2[20];
int tmp3[20];
int tmp4[20];
int tmp5[20];
int tmp6[20];
int tmp7[20];
int tmp8[20];
int tmp9[20];
int tmp10[20];
int tmp11[20];
int tmp12[20];
int tmp13[20];
void init()
{int i 0;int nums 0;for (i 0; i 20; i){nums rand() % 100;tmp1[i] nums;tmp2[i] nums;tmp3[i] nums;tmp4[i] nums;tmp5[i] nums;tmp6[i] nums;tmp7[i] nums;tmp8[i] nums;tmp9[i] nums;tmp10[i] nums;tmp11[i] nums;tmp12[i] nums;tmp13[i] nums;}
}
void test()
{int numsSize 20;InsertSort(tmp1, numsSize);//插入排序ShellSort(tmp2, numsSize);//希尔排序BubbleSort(tmp3, numsSize);//冒泡排序PartSort1(tmp4, 0, numsSize - 1);//快排1PartSort2(tmp5, 0, numsSize - 1);//快排2PartSort3(tmp6, 0, numsSize - 1);//快排3QuickSort(tmp7, 0, numsSize - 1);//快排改进QuickSortNonR(tmp8, 0, numsSize - 1);//快排非递归SelectSort(tmp9, numsSize);HeapSort(tmp10, numsSize);int* tmp (int*)malloc(sizeof(int) * numsSize);MergeSort(tmp11, 0, numsSize - 1, tmp);MergeSortNonR(tmp12, numsSize - 1, tmp);CountSort(tmp13, numsSize);free(tmp);
}
void print(int* nums, int numsSize)
{int i 0;for (i 0; i numsSize; i){printf(%d , nums[i]);}printf(\n);
}
void Print()
{print(tmp1, 20);print(tmp2, 20);print(tmp3, 20);print(tmp4, 20);print(tmp5, 20);print(tmp6, 20);print(tmp7, 20);print(tmp8, 20);print(tmp9, 20);print(tmp10, 20);print(tmp11, 20);print(tmp12, 20);print(tmp13, 20);
}
int main()
{srand((unsigned)time());//int nums[] { 3,9,0,-2,1 };//int numsSize sizeof(nums) / sizeof(nums[0]);//计算数组大小//sortArray(nums, numsSize);//调用排序算法init();//对排序的数组赋值test();//调用各个排序函数//print(nums, numsSize);//打印排序结果Print();//打印各个排序结果return 0;
}
