最新淘宝客网站程序,军人运动会官方网站建设目标,德州哪家网站优化好,wordpress 怎么设置主页目录 首言#xff1a; 1. 插入排序 1.1 直接插入排序 1.2 希尔排序
2. 选择排序 2.1 直接选择排序 2.2 堆排序
3. 交换排序 3.1 冒泡排序 3.2 快排 结尾#xff1a;
首言#xff1a; 本篇文章主要介绍常见的四大排序#xff1a;交换排序、选择排序、插入排序、归并排…目录 首言 1. 插入排序 1.1 直接插入排序 1.2 希尔排序
2. 选择排序 2.1 直接选择排序 2.2 堆排序
3. 交换排序 3.1 冒泡排序 3.2 快排 结尾
首言 本篇文章主要介绍常见的四大排序交换排序、选择排序、插入排序、归并排序。上主要介绍前三种。由常见的时间复杂度较大的再到复杂到较小的比较难的排序。由浅入深层层递进实现对排序的深刻理解. 1. 插入排序 1.1 直接插入排序 实现简单的插入排序需要我们首先进行单趟的排序。其基本思想为故名思意就是将尾部最后面位置的数插入到比他大的数的前面并将大的数据向后移动。方法为找到尾部的值定义为 end 1前面的值为 end , 然后进行判断的比较。 单趟排序实现的代码为将 end 赋值为 n - 2之后先前进行比较。
void Part_InitSort(int* a, int n)//a 表示一个数组n 表示这个数组的大小
{//进行单趟的排序找到末尾位置int end n - 2;//使它指向数组的倒数第二个int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}//当遇到小于 tmp 的值的时候跳出循环并且将 end 1 的位置放上 tmp。a[end 1] tmp;
} 之后将单趟排序放入到整个的排序之中去从第一个位置开始(先进行比较前面的两个数字)记录它的下标放到 tmp 里面如果是 tmp 小的话就进行移动。直到这个 n 表示的后面的倒数第二个的时候实现全部的排序。进行替换的时候循环结束的条件为到 end 减到 0 为止。
void InitSort(int* a, int n)
{//利用单趟插入的排序的想法进行一个循环的排序int i 0;for (i 0; i n - 1; i){//从前两个位置开始int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 1.2 希尔排序 由于直接插入排序的时间复杂度非常的高。对其进行优化现在给出这样一个变量 grap 进行划分不在一个一个的比较直接比较相差 grap 个数之后的数进行比较(进行预排)使用预排序可以实现使整个数组实现接近有序从而大大减少直接插入排序的次数。如图所示。 void ShellSort(int* a, int n)
{//首先我们先不考虑 grap 的大小假设为 3, 就是相当于将前面的位置的 1 换成了 grapint grap 3;for (int i 0; i n - grap; i){int tmp a[i grap];int end i;while (end 0){if (tmp a[end]){a[end grap] a[end];end - grap;}else{break;}}a[end grap] tmp;}//接下来就是对于 garp 的范围进行确定。
} 经过大量的实践得到了当每次 grap grap / 3 (grap n);进行的预排序时间复杂度是最好的。 进行 grap 的选择的时候具有如果 grap 很大但是跳的很快但是越不接近有序的特点。所以当不断缩小空间的时候由于前面的铺垫会让后面范围小的插入排序进行次数减少。但是希尔排序也具有不稳定的特点。 希尔排序进行结束的条件是grap 1,因为最后一次执行的就是直接插入排序但是因为接近有序了所以需要的次数非常的少。
void ShellSort(int* a, int n)
{//进行一次的希尔排序并不是已经排序好的是需要不断地去缩小空间实现排序//int grap n;while (grap 1){grap (grap / 3) 1;// 1 是为了保证最后一次始终有 1 for (int i 0; i n - grap; i){int tmp a[i grap];int end i;while (end 0){if (tmp a[end]){a[end grap] a[end];end - grap;}else{break;}}a[end grap] tmp;}}
}
2. 选择排序 2.1 直接选择排序 基本思想定义一个 tmp(用来进行遍历)每次都从第一个位置开始到 end 结束如果是a[tmp]大于定义的最大的内个,就将 tmp 赋值给最大的那个下标(小的也一样)。找到最大的最小的那个之后进行交换交换的时候最小的交换到第一个位置最小的交换到最后位置。随后进行 end--begin。在进行下一步操作。 注意选择排序的交换的是带有下标的数组元素不是直接的替换(直接替换的话会造成数据的串改)。下面这个串代码包括了选择排序与交换函数。
void SelectSort(int* a, int n)
{assert(a);int begin 0, end n - 1, i 0;for (i begin; i end; i){//需要寻找的是下标int mini begin, maxi end;int tmp begin;for (tmp begin 1; tmp end; tmp){if (a[tmp] a[maxi]){maxi tmp;}if (a[tmp] a[mini]){mini tmp;}}//在同时进行寻找 最大 与 最小 的时候可能会有最大值在第一个位置的情况.//最小值在开始位置时这不影响。但是最大值在一开始位置就影响。Swap(a[begin], a[mini]);//交换了之后mini 位置 存放的是最大值if (begin maxi){maxi mini;}Swap(a[maxi], a[end]);end--;begin;}
}
void Swap(int* a, int* b)
{int* tmp a;*a *tmp;*b *tmp;
} 2.2 堆排序 堆排序就是通过建立堆来进行排序。升序建立建大堆降序建小堆。 建堆的话需要进行向下调整算法实现大(小)堆。 1.向下调整算法(以建立大堆为例)要求左右子树都是小堆才可以使用向下调整算法。原理是通过父亲结点跟左右孩子节点进行比较如果是孩子比父亲大就需要进行交换接着向下走。直到父亲结点比所有的孩子都大的时候就停止。 2.细节循环结束的条件是child n因为识别的是数组的下标所有的大小都是 n - 1。其次跟新完父亲结点之后的孩子结点也是需要更新的。最后的退出条件为当父亲节点比所有的孩子结点都要大的时候就跳出循环表示大堆已经建立。
void AdjustDown(int* a, int n, int parent)
{int Child parent * 2 1;//找到左孩子.//当孩子不小于n就停止while (Child n){if (Child 1 n a[Child] a[Child 1])//找到孩子里面最大的一个{Child 1;}if (a[parent] a[Child]){Swap(a[parent], a[Child]);parent Child;Child parent * 2 1;}else//因为下面的就都是符合条件的,不需要在进行向下调整.{break;}}
}
2.通过这个算法在底部从下往上开始进行排序实现大堆的建立。建立完大堆之后将第一个位置的值放到最后一个位置。排序 n - 1个数。
注意事项1.建立大堆是需要从最后一个父亲结点向前进行向下调整算法。2. 注意 i 的范围是从 n - 1 - 1/ 2开始的 . 3. 下一次进来的时候是去排序 end 个数字。
//堆排序的时间复杂度为 n * log(n)
void HeapSort(int* a, int n)
{//堆排序建立升序用大堆。所以需要一个向下调整函数。//1.首先先建立一个大堆.int i 0;for (i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//2.将第一个位置的最大值放到堆的最后int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
3. 交换排序 3.1 冒泡排序 冒泡排序是最简单的交换排序从第一个位置开始向后进行一次交换直到找到了不符合条件的那个数字就停止。 注意实现i 表示的是进行多少次的交换主要看的是的 j 每次都是从 0第一个位置开始进行计算比较的是两个数字所以是 n - 1但是每次当放到最后的一个位置的时候会少一个数字所以每次都要- i
void BubbleSort(int* a, int n)
{assert(a);int i 0, j 0;for (i 0; i n ; i){for (j 0; j n - 1- i; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
} 3.2 快排 快速排序是经常会考到他的主要做法为定义 begin 和 end(倒数第二个数字),最后一个数字 key,begin 去找到比 key 大的数然后停下来end 去找比 key 小的数然后停下来。之后再进行交换比 key 大的值与比 key 小的值。当 begin end 的时候将 key 放到这个位置。
1. 首先先实现单趟的排序。
//函数的left 与 right 区间为[left, right]
int PartSort1(int* a, int left, int right)
{//选择一个 key我选择的是最后的位置所以就需要让 left 进行先走int key a[right];while (left right){//左边 去寻找最大的while (left right a[left] key){left;}//右边 去寻找最小的while (left right a[right] key){right--;}//每次进行寻找找到了 left 指向了较大的 right 指向较小的。就进行交换Swap(a[left], a[right]);}//结束循环时表示 left 与 left 相遇到了一起。随便与 k 进行交换可。Swap(a[key], a[right]);return left;//叫替换了的位置返回方便后续进行拆分
} 2. 通过单趟排序实现整体的快速排序。主要思想是通过递归让左右都实现有序不断的向下分直到不能分为止也就是只有一个数left 跟 right 都是在一起的时候表明这个一段数组是有序的。
void QuickSort(int* a, int left, int right)
{//每次都进行循环结束条件为左指针遇上了右指针.if (left right){return;}//每次递归都划分为两个区域left - div - 1,div 1 - right;int div PartSort2(a, left, right);//进行左边的排序QuickSort(a, left, div - 1);QuickSort(a, div 1, right);
} 3. 细节(1) 选定后面的值一定是从最前面的开始进行计算。因为前面去找的是最大的值需要将最大的值放到后面如果是右边先走的话就不是将最小的值放到后面因此 div 的右边就不是都大于 div 的。 (2) 当最后一次进行交换的时候会将 key 位置放到想要的位置它的前面都是小于 key 的后面都是大于 key 的。
(3) 其次当对于一个有序的数组直接的进行排序的话复杂度非常的高为O(n2)所以需要进行取中间值避免最后取到 key 的是极值的情况。这个取中间值的方法只要是运用在了进行部分的快速排序算法当中去。让 key 位置是保证为中间值不是极值。
int MidInit(int* a, int begin, int end)
{int mid (begin end )/2;if (a[begin] a[mid]){if (a[begin] a[end]){return begin;}else if (a[mid] a[end]){return mid;}else{return end;}}else //这种情况表示的是 a[begin] a[mid]{if (a[begin] a[end]){return begin;}else if (a[mid] a[end]){return mid;}else{return end;}}
}
(4) 快速排序还有另外的两种方法挖坑法 与 前后指针法以及再进行优化。这个一节我放到下一篇文章中进行讲解。 结尾 如果对你有帮助还请帮我点个免费的赞支持一下我我也会不断地改进争取写出跟高质量的文章。我们共同努力
