手机版网站开发框架,开题报告旅游网站建设,公司注册地址可以变更到外省吗,做网站的资源有哪些目录 排序的概念
1.直接插入排序
基本思想
代码实现
算法分析
2.希尔排序
基本思想
代码实现
算法分析
3.冒泡排序
基本思想 代码实现
算法分析
4.快速排序
基本思想
代码实现
算法分析
5.简单选择排序
基本思想
代码实现
算法分析
6.堆排序
基本思想
代…目录 排序的概念
1.直接插入排序
基本思想
代码实现
算法分析
2.希尔排序
基本思想
代码实现
算法分析
3.冒泡排序
基本思想 代码实现
算法分析
4.快速排序
基本思想
代码实现
算法分析
5.简单选择排序
基本思想
代码实现
算法分析
6.堆排序
基本思想
代码实现
算法分析
7.归并排序
基本思想
代码实现
算法分析
8.基数排序
基本思想
代码实现
算法分析 总结 排序的概念
排序所谓排序就是一串记录按照某个关键字的大小按照递增或者递减的顺序进行排列的操作。
稳定性排序的稳定性在排序前有许多相同关键字的记录他们是按照一定的次序排列的。在排序后还能按照原先的次序进行排序那么我们称这种排序算法是稳定的否则是不稳定的。
内部排序数据全部在内存中排序。
外部排序数据元素过多无法在内存中排序需要通过内外存之间移动数据来进行排序。
相关算法 1.直接插入排序
基本思想
直接插入排序是一种简单的插入排序思想是把待排序的记录按照其关键值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完成得到一个新的有序序列。 就比如说我们现实生活中的玩扑克牌的方式就用了这种思想我们每摸到一张牌的时候原先手上的牌是排好序的我们拿到这张新的牌会插入到原先的有序序列然后插入之后我们新的序列又是有序的。之后每次摸牌都按照这种方式最终会得到一个完全有序的序列。 代码实现
有两种一种是直接插入另一种是折半插入区别在于查找插入位置的方法不同而已。
//1.直接插入排序void InsertSort(int *a,int n){int j;for(int i1;in;i){if(a[i]a[i-1]){int tempa[i];for( ji-1;j0a[j]temp;j--){a[j1]a[j];}//找到temp需要插入的位置并将元素后以一个//j等于a[j1]temp;}}
}1.2.折半插入排序void InsertSort2(int *a,int n){int i,j,low,high,mid;for(i1;in;i){int tempa[i];low0;highi-1;while(lowhigh){mid(lowhigh)/2;if(a[mid]temp){highmid-1;}else{lowmid1;}}//of while找到插入的位置for(ji-1;jhigh1;j--){a[j1]a[j];}a[high1]temp;}
}
算法分析 首先我们先分析算法的时间复杂度要考虑算法的最好、最坏以及平均复杂度。最好的情况是当这个数组已经有序或者接近有序的情况下我们只需要进行比较不需要移动元素最好时间复杂度为O(N)。而最坏的情况是这个数组是完全逆序的时候我们每次比较后都要移动大量的元素最坏时间复杂度为O(N2)**平均复杂度为**O(N^2)。 那么这个算法的空间复杂度为O(1)因为只需要使用常量级别的空间。 最后这个算法是否稳定答案是稳定的。因为每次是从后往前依次比较不会改变原先的次序移动的过程中也是一个一个进行移动的。 2.希尔排序
基本思想 希尔排序也是插入排序中的一种因为其本质就是使用了插入排序我们从插入排序的结论中可以得出越接近有序的数组使用插入排序的效率越高。 希尔排序的思想就是使一个数组先部分有序最后在全局有序。那么如何实现部分有序呢我们可以对数组的元素按照某种规律进行分组分组后对组内的记录进行排序如何重复进行分组和排序当最终每组的成员只剩一个时在进行排序的时候就是使用了插入排序。 代码实现 我们定义了一个d变量这个变量是用来进行分组的当d大于0的时候每次排序其实都是在预排序也就是对分组内的成员进行排序d是间隔也就是将iidi2*d...依次进行排序之后d/2或者d/31按照某种规律最终d1的时候在进行排序就是进行了一次直接插入排序。 //2.希尔排序
void shellSort(int *a,int n){int i,j,d;for(dn/2;d1;dd/2){//分成不同的趟数第一趟分割dn/2for(id;in;i){//对每一堂的每个小组排序if(a[i]a[i-d]){int tempa[i];for(ji-d;j0a[j]temp;jj-d){a[jd]a[j];}a[jd]temp;}//of if}//of for2}//of for1
}
算法分析 希尔排序的时间复杂度是一个复杂的问题在Kunth所著的《计算机程序设计技巧》第3卷中利用大量的实验统计资料得出平均复杂度为O(N^1.25)到O(1.6 * N^1.25)。这里的就暂且不讨论该结果具体得出的方式。 希尔排序是否是稳定的算法呢答案是不稳定的因为我们在预排序的过程中我们会进行大量的跳动式的移动元素的值因此会导致不能按照原先的序列进行排序。 希尔排序中的d是如何取值的呢当成Shell也就是该算法的原作者提出取d d/2然后向下取整直到d1时。后来Kunth提出取d d/3 1 d/3向下取整的方式直到gap1时。这两种方式没有说哪个好哪个坏因此使用其中一个即可。 3.冒泡排序
基本思想 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列依次比较两个元素如果它们的顺序错误就把它们交换过来。如果遍历一遍数组发现没有进行交换故该数组已经有序就不需要再进行排序。 代码实现 该排序算法的代码实现也很简单每趟排序遍历一遍数组两两比较每一趟会将最小的值放在第一位。如果该趟排序没有元素交换则不需要再进行排序了。 //3.冒泡排序
void BubbleSort(int *a,int n){for(int i0;in;i){//总共要冒n躺for(int j0;jn-i;j){//每一趟比较前n-i个元素if(a[j]a[j1]){int tempa[j];a[j]a[j1];a[j1]temp;}}}
}
算法分析 时间复杂度当元素为逆序时需要进行n-1趟排序而每趟需要比较n-1次。故最坏时间复杂度为O(N^2)。当元素为有序时第一趟后发现不需要交换元素则只需要进行n-1次比较。故最好时间复杂度为O(N)。 空间也是仅使用了常数个辅助单元故空间复杂度为O(1)。 冒泡排序是一种稳定的算法。 4.快速排序
基本思想 快速排序是Hoare于1962年提出的一种以二叉树结构的交换排序。 其本质是基于分治法实现的基本思想是任取待排序元素序列中的某个元素作为基准按照该排序码将待排序集合分割成两子序列左子序列的所有元素均小于基准值右子序列均大于基准值。然后左右子序列重复该操作知道该序列有序为止。 代码实现 关于快速排序其实c语言的stdlib库中自带快排函数qsort()可以直接用详情请看 C语言学习--快速排序函数sqort()-CSDN博客 先将选定的基准值(最左边)直接取出然后留下一个坑当右指针遇到小于基准值的数时直接将该值放入坑中而右指针指向的位置形成新的坑位然后左指针遇到大于基准值的数时将该值放入坑中左指针指向的位置形成坑位重复该步骤直到左右指针相等。最后将基准值放入坑位之中。之后也是以基准值为界限递归排序基准值左右区间。 //4.快速排序
// 挖坑法
int PartSort(int* a, int begin, int end){int key a[begin];int piti begin;while (begin end){// 右边找小填到左边的坑里面去。这个位置形成新的坑while (begin end a[end] key){--end;}a[piti] a[end];piti end;// 左边找大填到右边的坑里面去。这个位置形成新的坑while (begin end a[begin] key){begin;}a[piti] a[begin];piti begin;}a[piti] key;return piti;
}
// 快速排序递归实现
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
算法分析 快速排序整体的综合性能与使用场景都是比较好的所以才能称为快速排序。时间复杂度在优化后基本上能达到O(N*logN)且优化后优势更加明显。 空间复杂度因为使用了递归导致空间复杂度为O(logN)。 算法是不稳定的。 5.简单选择排序
基本思想 就是每一次从待排序的数据元素中选择最小或者最大的元素放在序列的起始位置直到全部排序完毕。 代码实现
//5.简单选择排序
void SelectSort(int *a,int n){for(int i0;in-1;i){//n-1躺每一趟找一个最小值放到最前面int mini;//记录最小值所在的下标便于交换位置for(int ji1;jn;j){if(a[j]a[min]){minj;}}//最小值所在下标minint tempa[min];a[min]a[i];a[i]temp;//把每趟的最小值已到了最前面来}
}
每次找到最小最大的值记录当前的位置并且与开始位置进行交换。然后重复进行该操作直到集合中只剩一个元素为止。
算法分析 简单选择排序是比较简单的一种但是效率并不高无论是什么情况算法时间复杂度都为O(N^2)因此实际中很少使用。 空间复杂度为O(1)仅使用了常量级别的空间。 直接选择排序是否是稳定的算法呢答案是不稳定的在交换的过程中可能会导致相对次序进行改变。比如表L{2,2,1}经过第一趟排序后结果为L{1,2,2}显示已经和原先的次序不一致故该排序算法是不稳定的。 6.堆排序
后面三种堆排序归并排序和基数排序不太好实现我觉得理解原理就可以了
基本思想 在了解堆排序之前首先要知道堆这个数据结构。 堆是一颗完全二叉树满足根节点大于或者小于左右孩子结点。堆可以分为大根堆和小根堆。大根堆的最大元素存放在根结点任意一颗非根节点的值小于等于其双亲结点的值。而小根堆与大根堆恰好相反小根堆的根元素为最小。 大根堆可以存放在一个数组中节点下标i对应的左右孩子分别是2*i2*i1 那么堆排序的思想很简单首先在排序前将待排序的数组构建成为一个堆以大根堆为例将堆顶元素与堆底元素进行交换然后继续将堆顶元素进行向下调整然后保持大根堆的特性。因为对顶元素永远是当前堆中最大的一个将其放在最后就相当于把最大元素放在了数组的最后再将堆的范围缩小因此大根堆排序后的结果为升序。 代码实现 //6.堆排序
void swap(int* p1, int* p2){int tmp *p1;*p1 *p2;*p2 tmp;
}
// 堆排序
// 向下取整
void AdjustDwon(int* a, int n, int root){int child root * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[root]){swap(a[child], a[root]);root child;child root * 2 1;}else{break;}}
}
void HeapSort(int* a, int n){// 建堆方式2O(N)for (int i (n-2) / 2; i 0; --i){AdjustDwon(a, n, i);}// O(N*logN)int end n - 1;while (end 0){swap(a[0], a[end]);AdjustDwon(a, end, 0);--end;}
}算法分析 堆排序是一种效率很高的排序通过使用堆的数据结构来进行排序时间复杂度为O(N*logN)建堆的时间为O(N)然后有n-1次向下调整操作每次调整的时间复杂度与高度有关而hlog2n 1故时间复杂度为O(N*logN)。 空间也是仅使用了常数个辅助单元故空间复杂的为O(1)。 堆排序是否是稳定的算法呢答案是不稳定的在进行筛选的过程中可能把后面相同的元素调整到前面来。 7.归并排序
基本思想 归并排序是建立在归并操作上的一种有效的排序算法该算法采用的是分治法。其思想就是将序列分成n个子序列再使用子序列有序之后将其合并为一个新的有序表如果两个有序表合并为一个有序表称为二路归并。 代码实现
//7.归并排序
void _MergeSort(int* a, int begin, int end, int* tmp){int mid (begin end) / 2;// [begin, mid] [mid1, end] 分治递归让子区间有序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);//归并 [begin, mid] [mid1, end]int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] 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);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
算法分析
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。
每趟归并的时间为O(N)并且需要log2N趟归并所以时间复杂度为O(N*logN)。
二路归并排序不会改变相同关键字记录的相对次序因此是一种稳定的算法。 8.基数排序
基本思想
将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。这样说明比较难理解下面我们看一个图文解释理解基数排序的步骤
注意基数排序中不能出现负数
代码实现
//8.基数排序
//基数排序
void RadixSort(int* arr, int n){//max为数组中最大值int max arr[0];int base 1;//找出数组中的最大值for (int i 0; i n; i){if (arr[i] max){max arr[i];}}//循环结束max就是数组最大值//临时存放数组元素的空间int* tmp (int*)malloc(sizeof(int)*n);//循环次数为最大数的位数while (max / base 0){ //定义十个桶桶里面装的不是数据本身而是每一轮排序对应十、白、千...位的个数//统计每个桶里面装几个数int bucket[10] { 0 };for (int i 0; i n; i){//arr[i] / base % 10可以取到个位、十位、百位对应的数字bucket[arr[i] / base % 10];}//循环结束就已经统计好了本轮每个桶里面应该装几个数//将桶里面的元素依次累加起来就可以知道元素存放在临时数组中的位置for (int i 1; i 10; i){bucket[i] bucket[i - 1];}//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置//开始放数到临时数组tmpfor (int i n - 1; i 0; i--){tmp[bucket[arr[i] / base % 10] - 1] arr[i];bucket[arr[i] / base % 10]--;}//不能从前往后放因为这样会导致十位排好了个位又乱了百位排好了十位又乱了/*for (int i 0; i n; i){tmp[bucket[arr[i] / base % 10] - 1] arr[i];bucket[arr[i] / base % 10]--;}*///把临时数组里面的数拷贝回去for (int i 0; i n; i){arr[i] tmp[i];}base * 10;}free(tmp);
} 算法分析
基数排序的时间复杂度跟基数选取有关平均复杂度为O(k·n)。基数排序为稳定排序算法。 总结
