徐州营销网站建设报价,国外 上海网站建设,深圳网站设计公司有哪些,宁德市是哪个省现在我先将各大排序的动图和思路以及代码呈现给大家
插入排序
直接插入排序是一种简单的插入排序法#xff0c;其基本思想是#xff1a; 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为 止#xff0c;得到一个…
现在我先将各大排序的动图和思路以及代码呈现给大家
插入排序
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 实际中我们玩扑克牌时就用了插入排序的思想 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void InsertSort(int* a, int n)
{// [0,end]有序把end1位置的插入到前序序列// 控制[0,end1]有序for (size_t 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];}else{break;}--end;}a[end 1] tmp;}
}希尔排序
也称缩小增量排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达1时所有记录在统一组内排好序 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定
void ShellSort(int* a, int n)
{int gap n;while (gap 1){//gap gap / 2;gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}选择排序
2.2.1基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 2.2.2 直接选择排序: 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]集合中重复上述步骤直到集合剩余1个元素 直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
void InsertSort(int* a, int n)
{// [0,end]有序把end1位置的插入到前序序列// 控制[0,end1]有序for (size_t 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];}else{break;}--end;}a[end 1] tmp;}
}
堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种 它是 通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);// 继续往下调整parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆// O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排 序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动
冒泡排序 冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可 将区间按照基准值划分为左右两半部分的常见方式有
hoare版本 挖坑法 前后指针版本 快速排序优化三数取中法选key递归到小的子区间时可以考虑使用插入排序
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;// left mid rightif (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最大值{return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最小{return left;}else{return right;}}
}// Hoare
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){// 找小while (left right a[right] a[keyi]){--right;}// 找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
};// 挖坑法
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];// 保存key值以后左边形成第一个坑int hole left;while (left right){// 右边先走找小填到左边的坑右边形成新的坑位while (left right a[right] key){--right;}a[hole] a[right];hole right;// 左边再走找大填到右边的坑左边形成新的坑位while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}// 前后指针
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}
// [begin, end]
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)
归并排序
基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end begin)return;int mid (end begin) / 2;// [begin, mid][mid1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid1, end);// 归并到tmp数据组再拷贝回去// a-[begin, mid][mid1, end]-tmpint begin1 begin, end1 mid;int begin2 mid1, end2 end;int index begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] 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);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}根据自己的喜好进行数组的升序即可 这里不过多要求
