龙岗网站建设费用明细,住房城乡建设部官网,搭建网站干什么,百度网盟推广官方网站文章目录 1.排序概念及运用1.1 概念1.2 运用1.3 常见排序算法 2. 实现常见排序算法2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序2.1.2.1 希尔排序的时间复杂度计算 2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序 1.排序概念及运用
1.1 概念
排序#xff1a;所谓排序#x… 文章目录 1.排序概念及运用1.1 概念1.2 运用1.3 常见排序算法 2. 实现常见排序算法2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序2.1.2.1 希尔排序的时间复杂度计算 2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序 1.排序概念及运用
1.1 概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 1.2 运用
购物筛选排序 1.3 常见排序算法 2. 实现常见排序算法
2.1 插入排序 基本思想 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 2.1.1 直接插入排序
当插入第 i(i1) 个元素时前面的 array[0],array[1],…,array[i-1] 已经排好序此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移 代码实现
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#includestdlib.h
#includetime.h//打印
void PrintArr(int* arr, int n);//直接插入排序
void InsertSort(int* arr, int n);Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSort.h//打印
void PrintArr(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}//直接插入排序
//最差情况O(n^2)
//最好的情况:O(n
void InsertSort(int* arr, int n)
{//n-2for (int i 0; i n - 1; i){int end i;int tmp arr[end 1];while (end 0){if (arr[end] tmp){arr[end 1] arr[end];end--;}else {break;}}//end -1的时候跳出循环arr[end 1] arr[0]arr[end 1] tmp;}
}test.c
int main()
{int a[] { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n sizeof(a) / sizeof(int);printf(排序前);PrintArr(a, n);InsertSort(a,n);printf(排序后);PrintArr(a, n);return 0;
}直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N2)空间复杂度O(1) 2.1.2 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数通常是gap n/31把待排序文件所有记录分成各组所有的距离相等的记录分在同一组内并对每一组内的记录进行排序然后gapgap/31得到下一个整数再将数组分成各组进行插入排序当gap1时就相当于直接插入排序。它是在直接插入排序算法的基础上进行改进而来的综合来说它的效率肯定是要高于直接插入排序算法的。 第一趟排序n10gapn/25 分成五组每组都用直接插入排序。 end一开始放在9的位置上tmp放在4的位置上 第二趟排序gap5gapgap/312 分成两组每组都用直接插入排序。 end一开始放在4的位置上tmp放在2的位置上 第三趟排序gap2,gapgap/311 直接插入排序 希尔排序的特性总结 希尔排序是对直接插入排序的优化。 当 gap 1 时都是预排序目的是让数组更接近于有序。 当 gap 1 时数组已经接近有序的了直接插入排序。 代码实现
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#includestdlib.h
#includetime.h//打印
void PrintArr(int* arr, int n);//希尔排序
void ShellSort(int* arr, int n);Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSort.h//打印
void PrintArr(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}//希尔排序时间复杂度On^1.3)
void ShellSort(int* arr, int n)
{int gap n;//6while (gap 1){gap gap / 3 1;//保证最后一次gap一定为1for (int i 0; i n - gap; i)// i n - gap是为了防止下面的tmp访问数组元素越界{int end i;//n - gap - 1int tmp arr[end gap];//n - 1while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else {break;}}//也就是arr[end] tmp;arr[end gap] tmp;}}
}test.c
int main()
{int a[] { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n sizeof(a) / sizeof(int);printf(排序前);PrintArr(a, n);ShellSort(a,n);printf(排序后);PrintArr(a, n);return 0;
}2.1.2.1 希尔排序的时间复杂度计算
希尔排序的时间复杂度估算
外层循环
外层循环的时间复杂度可以直接给出为O(log2n) 或者O(log3n) 即O(log n)
内层循环 通过以上的分析可以画出这样的曲线图 因此希尔排序在最初和最后的排序的次数都为n即前一阶段排序次数是逐渐上升的状态当到达某一顶点时排序次数逐渐下降至n而该顶点的计算暂时无法给出具体的计算过程。
希尔排序时间复杂度不好计算因为 gap 的取值很多导致很难去计算因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语言版)》— 严蔚敏书中给出的时间复杂度为 2.2 选择排序
选择排序的基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
2.2.1 直接选择排序 在元素集合 array[i]--array[n-1] 中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的 array[i]--array[n-2]array[i1]--array[n-1] 集合中重复上述步骤直到集合剩余 1 个元素 代码实现
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#includestdlib.h
#includetime.h//打印
void PrintArr(int* arr, int n);//直接选择排序
void SelectSort(int* arr, int n);Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSort.h//交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//打印
void PrintArr(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}//直接选择排序
//时间复杂度为O(n^2)//优化前的
//将后面元素中最小的和第i个元素相比较比第i个元素小的就交换。
/*
void SelectSort(int* arr, int n) {for (int i 0; i n; i){int mini i;//找最小的for (size_t j i 1; j n; j) {if (arr[i] arr[mini]){mini i;}}//找到了最小值i和mini位置数据进行交换Swap(arr[i], arr[mini]);}
}
*///优化后的
//找到n个元素中最大和最小的分别给第一个和最后一个元素。
//然后在剩下来的元素里面找最大和最小的分别给第一个和最后一个元素。
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}//mini begin//maxi end//避免maxi begini都在同一个位置begin和mini交换之后maxi数据变成了最小的数据if (maxi begin){maxi mini;}Swap(arr[mini], arr[begin]);//最小的放到beginSwap(arr[maxi], arr[end]);//最大的放到endbegin;--end;}}test.c
int main()
{int a[] { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n sizeof(a) / sizeof(int);printf(排序前);PrintArr(a, n);SelectSort(a,n);printf(排序后);PrintArr(a, n);return 0;
}直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N2 )空间复杂度O(1) 2.2.2 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。在二叉树章节我们已经实现过堆排序这里不再赘述。
