金融跟单公司网站建设,js插件打开wordpress,如何开发高端市场,山西省经济建设投资公司网站目录
排序的概念
常见排序集锦 1.直接插入排序 2.希尔排序 3.选择排序 4.堆排序 5.冒泡排序 6.快速排序 hoare 挖坑法 前后指针法 非递归 7.归并排序 非递归
排序实现接口
算法复杂度与稳定性分析 排序的概念 排序 #xff1a;所谓排序#xff0c;就是使一串记录#…目录
排序的概念
常见排序集锦 1.直接插入排序 2.希尔排序 3.选择排序 4.堆排序 5.冒泡排序 6.快速排序 hoare 挖坑法 前后指针法 非递归 7.归并排序 非递归
排序实现接口
算法复杂度与稳定性分析 排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 这里推荐一个网站 数据结构和算法动态可视化 (Chinese) - VisuAlgo
它可以让我们更加清晰的看清楚排序的过程。
排序实现接口 sort.h
#includestdlib.h
#includestdio.h
#includeassert.h
#includetime.h// 插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n)// 快速排序递归实现// 1.快速排序hoare版本
int PartSort1(int* a, int left, int right);// 2.快速排序挖坑法
int PartSort2(int* a, int left, int right);// 3.快速排序前后指针法
int PartSort3(int* a, int left, int right);void QuickSort(int* a, int left, int right);// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)// 归并排序递归实现
void MergeSort(int* a, int n)// 归并排序非递归实现
void MergeSortNonR(int* a, int n) 1.插入排序
思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 实现 void InsertSort(int* arr, int n)
{// i n-1 最后一个位置就是 n-2for (int i 0; i n - 1; i){//[0,end]的值有序把end1位置的值插入保持有序int end i;int tmp arr[end 1];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];end--;}else{break;}}arr[end 1] tmp; // why? end1 //break 跳出 插入 因为上面end--//为什么不在else那里插入因为极端环境下假设val 0那么end-- 是-1不进入while //所以要在外面插入}
} 为什么这里 for 循环 i n-1 ? 如图所示 2.希尔排序
希尔排序又称缩小增量法思想 算法先将要排序的一组数按某个增量 gap 分成若干组每组中记录的下标相差 gap .对每组中全部元素进行排序然后再用一个较小的增量对它进行分组在每组中再进行排序。当增量减到1时 直接插入排序整个要排序的数被分成一组排序完成。
希尔排序可以理解为两个步骤1.预排序 2.直接插入排序 如下图 实现① void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1; //gap gap / 2;for (int j 0; j gap; j){for (int i j; i n - gap; i i gap){int end i;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end end - gap;}else{break;}}arr[end gap] tmp;}}
}
②在①的基础上进行简单的优化 void ShellSort(int* arr, int n)
{//gap 1 时 预排序//gap 1 时直接插入排序int gap n;while (gap 1){gap gap / 3 1; //加1意味着最后一次一定是1 当gap 1 时就是直接排序//gap gap / 2;for (int i 0; i n - gap; i){int end i;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end end - gap;}else{break;}}arr[end gap] tmp;}}}
为什么for循环内i n-gap ? gap的取值
这里看个人习惯上述中是gap一开始为n进入循环后每次 /3 之所以1是为了保证最后一次循环gap一定为1。当然 /2 也是可以的/2 就可以最后不用1。
希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 3. 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算希尔排序的时间复杂度都不固定。 4.排升序gap 越大大的数更快到后面小的数可以更快到前面但是越不接近有序 gap越小越接近有序 当gap 1 时就是直接插入排序。 3.选择排序
思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
实现这里简单做了一下优化每次遍历不仅仅选出最小的也选出最大的。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void SelectSort(int* arr, int n)
{assert(arr);int left 0; //开始位置int right n - 1; //结束位置while (left right){int min left;int max left;for (int i left 1; i right; i){if (arr[i] arr[min])min i;if (arr[i] arr[max])max i;}Swap(arr[left], arr[min]);//如果 left 和 max 重叠 那么要修正 max 的位置if (left max){max min;}Swap(arr[right], arr[max]);left;right--;}} 4.堆排序
思想堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 实现建堆方式有两种这里采用向下调整方式建堆
typedef int HPDataType;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustDown(HPDataType* arr, int size, int parent)//向下调整
{int child parent * 2 1;while (child size){if (arr[child 1] arr[child] child 1 size){child;}if (arr[child] arr[parent]){Swap((arr[child]), (arr[parent]));parent child;child (parent * 2) 1;}else{break;}}}void HeapSort(int* arr, int n)
{//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}//排序int end n - 1;while (end 0){Swap((arr[0]), (arr[end]));AdjustDown(arr, end, 0);end--;}} 5.冒泡排序
思想根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置冒泡排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
可参考冒泡
实现
void BubbleSort(int* arr, int n)
{assert(arr);for (int i 0; i n; i){int flag 1;for (int j 0; j n - i - 1; j){if (arr[j] arr[j 1]){Swap(arr[j], arr[j 1]);flag 0;}}//如果没有发生交换说明有序直接跳出if (flag 1)break;}} 6.快速排序
思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
hoare版本 方法如下
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}int PartSort1(int* arr, int begin, int end)
{int left begin;int right end;//keyi 意味着保存的是 key 的位置int keyi left;while (left right){//右边先走找小while (left right arr[right] arr[keyi]){right--;}//左边再走找大while (left right arr[left] arr[keyi]){left;}//走到这里意味着右边的值比 key 小左边的值比 key 大Swap(arr[left], arr[right]);}//走到这里 left 和 right 相遇 Swap(arr[keyi], arr[left]);keyi left; //需要改变keyi的位置return keyi;
} 挖坑法 方法如下
int PartSort2(int* arr, int begin, int end)
{int key arr[begin];int piti begin;while (begin end){//右边先走找小,填到左边的坑里去这个位置形成新的坑while (begin end arr[end] key){end--;}arr[piti] arr[end];piti end;//左边再走找大while (begin end arr[begin] key){begin;}arr[piti] arr[begin];piti begin;}//相遇一定是在坑位arr[piti] key;return piti;} 前后指针法 方法如下
int PartSort3(int* arr, int begin, int end)
{int key begin;int prev begin;int cur begin 1;//优化-三数取中int midi GetMidIndex(arr, begin, end);Swap(arr[key], arr[midi]);while (cur end){if (arr[cur] arr[key] prev ! cur ){prev;Swap(arr[prev], arr[cur]);}cur;}Swap(arr[key], arr[prev]);key prev;return key;
} 实现以上三种方法都是采用函数的方式实现这样方便调用。另外以上方法都是单趟排序如果要实现完整的排序还是要采用递归的方法类似于二叉树的前序遍历
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void QuickSort(int* arr, int begin,int end)
{//当区间不存在或者区间只要一个值递归返回条件if (begin end){return;}if (end - begin 20) //小区间优化一般在十几{//int keyi PartSort1(arr, begin, end);//int keyi PartSort2(arr, begin, end);int keyi PartSort3(arr, begin, end);//[begin , keyi - 1] keyi [keyi 1 , end]//如果 keyi 的左区间有序 右区间有序那么整体就有序QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi 1, end);}else{InsertSort(arr begin, end - begin 1);//为什么begin因为排序不仅仅排序左子树还有右子树//为什么1 因为这个区间是左闭右闭的区间.例0-9 是10个数 所以1}
} 优化 1. 三数取中法选key 2. 递归到小的子区间时可以考虑使用插入排序已在实现中使用 int GetMidIndex(int* arr, int begin, int end)
{//begin mid endint mid (begin end) / 2;if (arr[begin] arr[mid]){if (arr[mid] arr[end]){return mid;}else if(arr[begin] arr[end]) //走到这里说明 mid 是最大的{return end;}else{return begin;}}else // arr[begin] arr[mid]{if (arr[mid] arr[end]){return mid;}else if (arr[begin] arr[end]) // 走到这里就是 begin end 都大于 mid{return begin;}else{return end;}}
} 非递归版本
非递归版本需要用到栈这里是用c语言实现所以需要手动实现一个栈
如果使用c的话可以直接引用栈。
这里栈的实现暂时省略后期会给出链接。这里暂时知道一下就行。 简图 //非递归
//递归问题极端场景下深度太深会出现栈溢出
//1.直接改成循环--例斐波那契数列、归并排序
//2.用数据结构栈模拟递归过程
void QuickSortNonR(int* arr, int begin, int end)
{ST st;StackInit(st);StackPush(st, end);StackPush(st, begin);while (!StackEmpty(st)){int left StackTop(st);StackPop(st);int right StackTop(st);StackPop(st);int keyi PartSort3(arr, left, right);//[left , keyi - 1] keyi [keyi 1 , right]if (keyi 1 right){StackPush(st, right);StackPush(st, keyi 1);}if (left keyi - 1){StackPush(st, keyi - 1);StackPush(st, left);}}StackDestory(st);
} 7.归并排序
思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 实现
void _MergeSort(int* arr, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;//[begin mid] [mid1,end]//递归_MergeSort(arr, begin, mid, tmp);_MergeSort(arr, mid 1, end, tmp);//归并[begin mid] [mid1,end]int left1 begin;int right1 mid;int left2 mid 1;int right2 end;int i begin;//这里之所以等于begin 而不是等于0 是因为可能是右子树而不是左子树 i为tmp数组下标while (left1 right1 left2 right2){if (arr[left1] arr[left2]){tmp[i] arr[left1];}else{tmp[i] arr[left2];}}//假如一个区间已经结束另一个区间直接拿下来while (left1 right1){tmp[i] arr[left1];}while (left2 right2){tmp[i] arr[left2];}//把归并的数据拷贝回原数组 [begin mid] [mid1,end]// begin 是因为可能是右子树 例[2,3][4,5]//1 是因为是左闭右闭的区间 0-9 是10个数据memcpy(arr begin, tmp begin, (end - begin 1) * sizeof(int));}void MergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}_MergeSort(arr, 0, n - 1, tmp);free(tmp);
} 非递归版本
思想这里不能使用栈或者队列因为栈或者队列适合前序遍历的替换但是归并排序的思想属于后序遍历栈和队列的特性导致后期可能无法使用前面的空间。 这里因为是循环所以可以设计一个变量 gap当gap 1 就一一进行归并当gap 2时就两两进行归并gap 每次 *2 。
如图 代码如下
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){//[i , i gap-1] [i gap , i 2*gap-1]int left1 i;int right1 i gap - 1;int left2 i gap;int right2 i 2 * gap - 1;int j left1;while (left1 right1 left2 right2){if (arr[left1] arr[left2]){tmp[j] arr[left1];}else{tmp[j] arr[left2];}}while (left1 right1){tmp[j] arr[left1];}while (left2 right2){tmp[j] arr[left2];}}memcpy(arr, tmp, sizeof(int) * n);gap * 2;}free(tmp);
} 但是上述代码涉及到一个问题因为假设要排序的数据不是2的次方倍就会产生问题和数据的奇偶无关就会越界。
例 所以我们需要对代码进行优化 优化可以从两个方面进行
//1.归并完成全部拷贝回原数组 //采用修正边界的方法 //例如果是9个数据 最后一个数据也要继续进行归并 //因为如果不归并的话最后一次会全部拷贝回原数组也就意味着9个数据前8个归并拷贝回去的最后一个数据因为没有进行归并而产生随机值。
//如果越界就修正边界继续进行归并
代码如下
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}int gap 1;while (gap n){//printf(gap%d-, gap);for (int i 0; i n; i 2 * gap){//[i , i gap-1] [i gap , i 2*gap-1]int left1 i;int right1 i gap - 1;int left2 i gap;int right2 i 2 * gap - 1;//监测是否出现越界//printf([%d,%d][%d,%d]---, left1, right1, left2, right2);//修正边界if (right1 n){right1 n - 1;//[left2 , right2] 修正为一个不存在的区间left2 n;right2 n - 1;}else if (left2 n){left2 n;right2 n - 1;}else if (right2 n){right2 n - 1;}//printf([%d,%d][%d,%d]---, left1, right1, left2, right2);int j left1;while (left1 right1 left2 right2){if (arr[left1] arr[left2]){tmp[j] arr[left1];}else{tmp[j] arr[left2];}}while (left1 right1){tmp[j] arr[left1];}while (left2 right2){tmp[j] arr[left2];}}//printf(\n);memcpy(arr, tmp, sizeof(int) * n);gap * 2;}free(tmp);
}
2.归并一组数据就拷贝一组数据回原数组
这样如果越界就直接break跳出循环后面的数据不进行归并。
void MergeSortNonR_2(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){//[i , i gap-1] [i gap , i 2*gap-1]int left1 i;int right1 i gap - 1;int left2 i gap;int right2 i 2 * gap - 1;//right1 越界 或者 left2 越界则不进行归并if (right1 n || left2 n){break;}else if (right2 n){right2 n - 1;}int m right2 - left1 1;//实际归并个数int j left1;while (left1 right1 left2 right2){if (arr[left1] arr[left2]){tmp[j] arr[left1];}else{tmp[j] arr[left2];}}while (left1 right1){tmp[j] arr[left1];}while (left2 right2){tmp[j] arr[left2];}memcpy(arri, tmpi, sizeof(int) * m);}gap * 2;}free(tmp);
}
以上两种方式的代码皆可具体重要的还是思想。 算法复杂度与稳定性分析 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。
