网站新闻对百度优化有用吗,宁波网站建设服务提供商,旅游网站设计与制作课程设计,营销软件有哪些一、概述 排序有内部排序和外部排序#xff0c;内部排序是数据记录在内存中进行排序#xff0c;而外部排序是因排序的数据很大#xff0c;一次不能容纳全部的排序记录#xff0c;在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大#xff0c;则应采…一、概述 排序有内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大则应采用时间复杂度为O(nlog2n)的排序方法快速排序、堆排序或归并排序序。 快速排序是目前基于比较的内部排序中被认为是最好的方法当待排序的关键字是随机分布时快速排序的平均时间最短。 下面我们来分别介绍这8中排序算法。 二、排序算法 1、插入排序——直接插入排序 使用场景 经常碰到这样一类排序问题把新的数据插入到已经排好的数据列中。 基本思想 1将第一个数和第二个数排序然后构成一个有序序列 2将第三个数插入进去构成一个新的有序序列 3对第四个数、第五个数……直到最后一个数重复第二步。 实现逻辑 1首先设定插入次数即循环次数for(int i1;ilength;i)1个数的那次不用插入 2设定插入数和得到已经排好序列的最后一个数的位数。insertNum和ji-1 3从最后一个数开始向前循环如果插入数小于当前数就将当前数向后移动一位 4将当前数放置到空着的位置即j1。 代码示例 public void insertSort(int[] a){int lengtha.length;//数组长度将这个提取出来是为了提高速度。int insertNum;//要插入的数for(int i1;ilength;i){//插入的次数insertNuma[i];//要插入的数int ji-1;//已经排序好的序列元素个数while(j0a[j]insertNum){//序列从后到前循环将大于insertNum的数向后移动一格a[j1]a[j];//元素移动一格j--;}a[j1]insertNum;//将需要插入的数放在要插入的位置。}} 2、插入排序——希尔排序 使用场景 对于直接插入排序问题数据量巨大时。 基本思想 1将数的个数设为n取奇数kn/2将下标差值为k的书分为一组构成有序序列 2再取kk/2 将下标差值为k的书分为一组构成有序序列 3重复第二步直到k1执行简单插入排序。 实现逻辑 1首先确定分的组数。 2然后对组中元素进行插入排序。 3然后将length/2重复1,2步直到length0为止。 代码示例 public void sheelSort(int[] a){int d a.length;while (d!0) {dd/2;for (int x 0; x d; x) {//分的组数for (int i x d; i a.length; i d) {//组中的元素从第二个数开始int j i - d;//j为有序序列最后一位的位数int temp a[i];//要插入的元素for (; j 0 temp a[j]; j - d) {//从后往前遍历。a[j d] a[j];//向后移动d位}a[j d] temp;}}}}3、选择排序——简单选择排序 使用场景 常用于取序列中最大最小的几个数时。 基本思想 如果每次比较都交换那么就是交换排序如果每次比较完一个循环再交换就是简单选择排序。 1在要排序的一组数中选出最小或者最大的一个数与第1个位置的数交换 2然后在剩下的数当中再找最小或者最大的与第2个位置的数交换 3依次类推直到第n-1个元素倒数第二个数和第n个元素最后一个数比较为止。 实现逻辑 1首先确定循环次数并且记住当前数字和当前位置 2将当前位置后面所有的数与当前数字进行对比小数赋值给key并记住小数的位置 3比对完成后将最小的值与第一个数的值交换 4重复2、3步。 代码示例 public void selectSort(int[] a) {int length a.length;for (int i 0; i length; i) {//循环次数int key a[i];int positioni;for (int j i 1; j length; j) {//选出最小的值和位置if (a[j] key) {key a[j];position j;}}a[position]a[i];//交换位置a[i]key;}} 简单选择排序的改进——二元选择排序 简单选择排序每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素当前趟最大和最小记录的位置从而减少排序所需的循环次数。改进后对n个数据进行排序最多只需进行[n/2]趟循环即可。 代码示例 void SelectSort(int r[],int n) { int i ,j , min ,max, tmp; for (i1 ;i n/2;i) { // 做不超过n/2趟选择排序 min i; max i ; //分别记录最大和最小关键字记录位置 for (j i1; j n-i; j) { if (r[j] r[max]) { max j ; continue ; } if (r[j] r[min]) { min j ; } } //该交换操作还可分情况讨论以提高效率 tmp r[i-1]; r[i-1] r[min]; r[min] tmp; tmp r[n-i]; r[n-i] r[max]; r[max] tmp; }
} 4、选择排序——堆排序 堆排序是一种树形选择排序是对直接选择排序的有效改进。 使用场景 对简单选择排序的优化。 基本思想 堆的定义如下具有n个元素的序列k1,k2,...,kn),当且仅当满足 时称之为堆。由堆的定义可以看出堆顶元素即第一个元素必为最小项小顶堆。 若以一维数组存储一个堆则堆对应一棵完全二叉树且所有非叶结点的值均不大于(或不小于)其子女的值根结点堆顶元素的值是最小(或最大)的。如 a大顶堆序列96, 83,27,38,11,09) b小顶堆序列1236248547305391 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树一维数组存储二叉树调整它们的存储序使之成为一个堆将堆顶元素输出得到n 个元素中最小(或最大)的元素这时堆的根节点的数最小或者最大。然后对前面(n-1)个元素重新调整使之成为堆输出堆顶元素得到n 个元素中次小(或次大)的元素。依此类推直到只有两个节点的堆并对它们作交换最后得到有n个节点的有序序列。称这个过程为堆排序。 因此实现堆排序需解决两个问题 1、如何将n 个待排序的数建成堆 2、输出堆顶元素后怎样调整剩余n-1 个元素使其成为一个新堆。 首先讨论第二个问题输出堆顶元素后对剩余n-1元素重新建成堆的调整过程。 调整小顶堆的方法 1设有m 个元素的堆输出堆顶元素后剩下m-1 个元素。将堆底元素送入堆顶最后一个元素与堆顶进行交换堆被破坏其原因仅是根结点不满足堆的性质。 2将根结点与左、右子树中较小元素的进行交换。 3若与左子树交换如果左子树堆被破坏即左子树的根结点不满足堆的性质则重复方法 2. 4若与右子树交换如果右子树堆被破坏即右子树的根结点不满足堆的性质。则重复方法 2. 5继续对不满足堆性质的子树进行上述交换操作直到叶子结点堆被建成。 称这个自根结点到叶子结点的调整过程为筛选。如图 再讨论对n 个元素初始建堆的过程。 建堆方法对初始序列建堆的过程就是一个反复进行筛选的过程。 1n 个结点的完全二叉树则最后一个结点是第个结点的子树。 2筛选从第个结点为根的子树开始该子树成为堆。 3之后向前依次对各结点为根的子树进行筛选使之成为堆直到根结点。 如图建堆初始过程无序序列4938659776132749 具体步骤1将序列构建成大顶堆 2将根节点与最后一个节点交换然后断开最后一个节点 3重复第一、二步直到所有节点断开。 代码示例 public void heapSort(int[] a){System.out.println(开始排序);int arrayLengtha.length;//循环建堆 for(int i0;iarrayLength-1;i){//建堆 buildMaxHeap(a,arrayLength-1-i);//交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i);System.out.println(Arrays.toString(a));}}private void swap(int[] data, int i, int j) {// TODO Auto-generated method stub int tmpdata[i];data[i]data[j];data[j]tmp;}//对data数组从0到lastIndex建大顶堆 private void buildMaxHeap(int[] data, int lastIndex) {// TODO Auto-generated method stub //从lastIndex处节点最后一个节点的父节点开始 for(int i(lastIndex-1)/2;i0;i--){//k保存正在判断的节点 int ki;//如果当前k节点的子节点存在 while(k*21lastIndex){//k节点的左子节点的索引 int biggerIndex2*k1;//如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在 if(biggerIndexlastIndex){//若果右子节点的值较大 if(data[biggerIndex]data[biggerIndex1]){//biggerIndex总是记录较大子节点的索引 biggerIndex;}}//如果k节点的值小于其较大的子节点的值 if(data[k]data[biggerIndex]){//交换他们 swap(data,k,biggerIndex);//将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值 kbiggerIndex;}else{break;}}}} 5、交换排序——冒泡排序 使用场景 一般不用。 基本思想 1将序列中所有元素两两比较将最大的放在最后面 2将剩余序列中所有元素两两比较将最大的放在最后面 3重复第二步直到只剩下一个数。 实现逻辑 1设置循环次数 2设置开始比较的位数和结束的位数 3两两比较将最小的放到前面去 4重复2、3步直到循环次数完毕。 代码示例 public void bubbleSort(int[] a){int lengtha.length;int temp;for(int i0;ia.length;i){for(int j0;ja.length-i-1;j){if(a[j]a[j1]){tempa[j];a[j]a[j1];a[j1]temp;}}}} 冒泡排序算法的改进 对冒泡排序常见的改进方法是加入一标志性变量exchange用于标志某一趟排序过程中是否有数据交换如果进行某一趟排序时并没有进行数据交换则说明数据已经按要求排列好可立即结束排序避免不必要的比较过程。本文再提供以下两种改进算法 1、设置一标志性变量pos用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。 代码示例 void Bubble_1 ( int r[], int n) { int i n -1; //初始时,最后位置保持不变 while ( i 0) { int pos 0; //每趟开始时,无记录交换 for (int j 0; j i; j) if (r[j] r[j1]) { pos j; //记录交换的位置 int tmp r[j]; r[j]r[j1];r[j1]tmp; } i pos; //为下一趟排序作准备 }
}
2、传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) 从而使排序趟数几乎减少了一半。代码示例 void Bubble_2 ( int r[], int n){ int low 0; int high n -1; //设置变量的初始值 int tmp,j; while (low high) { for (j low; j high; j) //正向冒泡,找到最大者 if (r[j] r[j1]) { tmp r[j]; r[j]r[j1];r[j1]tmp; } --high; //修改high值, 前移一位 for ( jhigh; jlow; --j) //反向冒泡,找到最小者 if (r[j]r[j-1]) { tmp r[j]; r[j]r[j-1];r[j-1]tmp; } low; //修改low值,后移一位 }
} 6、交换排序——快速排序 使用场景 要求时间最快时。 基本思想 1选择一个基准元素,通常选择第一个元素或者最后一个元素, 2通过一趟排序讲待排序的记录分割成独立的两部分其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。 3此时基准元素在其排好序后的正确位置 4然后分别对这两部分记录用同样的方法继续进行排序直到整个序列有序。 一趟排序的过程 排序的全过程 代码示例
public static void quickSort(int[] numbers, int start, int end) { if (start end) { int base numbers[start]; // 选定的基准值第一个数值作为基准值 int temp; // 记录临时中间值 int i start, j end; do { while ((numbers[i] base) (i end)) i; while ((numbers[j] base) (j start)) j--; if (i j) { temp numbers[i]; numbers[i] numbers[j]; numbers[j] temp; i; j--; } } while (i j); if (start j) quickSort(numbers, start, j); if (end i) quickSort(numbers, i, end); }
} 分析 快速排序是通常被认为在同数量级O(nlog2n)的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时快排序反而蜕化为冒泡排序。为改进之通常以“三者取中法”来选取基准记录即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。 快速排序的改进 在本改进算法中只对长度大于k的子序列递归调用快速排序让原序列基本有序然后再对整个基本有序序列用插入排序算法排序。实践证明改进后的算法时间复杂度有所降低且当k取值为 8 左右时,改进算法的性能最佳。 代码示例 void print(int a[], int n){ for(int j 0; jn; j){ couta[j] ; } coutendl;
} void swap(int *a, int *b)
{ int tmp *a; *a *b; *b tmp;
} int partition(int a[], int low, int high)
{ int privotKey a[low]; //基准元素 while(low high){ //从表的两端交替地向中间扫描 while(low high a[high] privotKey) --high; //从high 所指位置向前搜索至多到low1 位置。将比基准元素小的交换到低端 swap(a[low], a[high]); while(low high a[low] privotKey ) low; swap(a[low], a[high]); } print(a,10); return low;
} void qsort_improve(int r[ ],int low,int high, int k){ if( high -low k ) { //长度大于k时递归, k为指定的数 int pivot partition(r, low, high); // 调用的Partition算法保持不变 qsort_improve(r, low, pivot - 1,k); qsort_improve(r, pivot 1, high,k); }
}
void quickSort(int r[], int n, int k){ qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序 //再用插入排序对基本有序序列排序 for(int i1; in;i ){ int tmp r[i]; int ji-1; while(tmp r[j]){ r[j1]r[j]; jj-1; } r[j1] tmp; } } int main(){ int a[10] {3,1,5,7,2,4,9,6,10,8}; cout初始值; print(a,10); quickSort(a,9,4); cout结果; print(a,10); }7、归并排序 使用场景 速度仅次于快排内存少的时候使用可以进行并行计算的时候使用。 基本思想 1选择相邻两个数组成一个有序序列 2选择相邻的两个有序序列组成一个有序序列 3重复第二步直到全部组成一个有序序列。 实现逻辑 设r[i…n]由两个有序子表r[i…m]和r[m1…n]组成两个子表长度分别为n-i 1、n-m。 1、jm1kiii; //置两个子表的起始下标及辅助数组的起始下标 2、若im 或jn转⑷ //其中一个子表已合并完比较选取结束 3、//选取r[i]和r[j]较小的存入辅助数组rf 如果r[i]r[j]rf[k]r[i] i k 转⑵ 否则rf[k]r[j] j k 转⑵ 4、//将尚未处理完的子表中元素存入rf 如果im将r[i…m]存入rf[k…n] //前一子表非空 如果jn , 将r[j…n] 存入rf[k…n] //后一子表非空 5、合并结束。 代码示例
public static void mergeSort(int[] numbers, int left, int right) { int t 1;// 每组元素个数 int size right - left 1; while (t size) { int s t;// 本次循环每组元素个数 t 2 * s; int i left; while (i (t - 1) size) { merge(numbers, i, i (s - 1), i (t - 1)); i t; } if (i (s - 1) right) merge(numbers, i, i (s - 1), right); }
}
private static void merge(int[] data, int p, int q, int r) { int[] B new int[data.length]; int s p; int t q 1; int k p; while (s q t r) { if (data[s] data[t]) { B[k] data[s]; s; } else { B[k] data[t]; t; } k; } if (s q 1) B[k] data[t]; else B[k] data[s]; for (int i p; i r; i) data[i] B[i];
} 归并的迭代算法 1 个元素的表总是有序的。所以对n 个元素的待排序列每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表所得子表除最后一个子表长度可能为1 外其余子表长度均为2。再进行两两合并直到生成n 个元素按关键码有序的表。 代码示例 void print(int a[], int n){ for(int j 0; jn; j){ couta[j] ; } coutendl;
} //将r[i…m]和r[m 1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{ int j,k; for(jm1,ki; im j n ; k){ if(r[j] r[i]) rf[k] r[j]; else rf[k] r[i]; } while(i m) rf[k] r[i]; while(j n) rf[k] r[j]; print(rf,n1);
} void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ int len 1; ElemType *q r ; ElemType *tmp ; while(len lenght) { int s len; len 2 * s ; int i 0; while(i len lenght){ Merge(q, rf, i, i s-1, i len-1 ); //对等长的两个子表合并 i i len; } if(i s lenght){ Merge(q, rf, i, i s -1, lenght -1); //对不等长的两个子表合并 } tmp q; q rf; rf tmp; //交换q,rf以保证下一趟归并时仍从q 归并到rf }
} int main(){ int a[10] {3,1,5,7,2,4,9,6,10,8}; int b[10]; MergeSort(a, b, 10); print(b,10); cout结果; print(a,10); } 两路归并的迭代算法代码示例 void MSort(ElemType *r, ElemType *rf,int s, int t)
{ ElemType *rf2; if(st) r[s] rf[s]; else { int m(st)/2; /*平分*p 表*/ MSort(r, rf2, s, m); /*递归地将p[s…m]归并为有序的p2[s…m]*/ MSort(r, rf2, m1, t); /*递归地将p[m1…t]归并为有序的p2[m1…t]*/ Merge(rf2, rf, s, m1,t); /*将p2[s…m]和p2[m1…t]归并到p1[s…t]*/ }
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{ /*对顺序表*p 作归并排序*/ MSort(r, rf,0, n-1);
} 8、基数排序 使用场景 用于大量数很长的数进行排序时。 基本思想 1将所有的数的个位数取出按照个位数进行排序构成一个序列 2将新构成的所有的数的十位数取出按照十位数进行排序构成一个序列。 代码示例 public void sort(int[] array) {//首先确定排序的趟数; int max array[0];for (int i 1; i array.length; i) {if (array[i] max) {max array[i];}}int time 0;//判断位数; while (max 0) {max / 10;time;}//建立10个队列; ListArrayList queue new ArrayListArrayList();for (int i 0; i 10; i) {ArrayListInteger queue1 new ArrayListInteger();queue.add(queue1);}//进行time次分配和收集; for (int i 0; i time; i) {//分配数组元素; for (int j 0; j array.length; j) {//得到数字的第time1位数; int x array[j] % (int) Math.pow(10, i 1) / (int) Math.pow(10, i);ArrayListInteger queue2 queue.get(x);queue2.add(array[j]);queue.set(x, queue2);}int count 0;//元素计数器; //收集队列元素; for (int k 0; k 10; k) {while (queue.get(k).size() 0) {ArrayListInteger queue3 queue.get(k);array[count] queue3.get(0);queue3.remove(0);count;}}}} 三、总结 各种排序的稳定性时间复杂度和空间复杂度总结 我们比较时间复杂度函数的情况 时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说 1平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序 2线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序 3O(n1§))排序,§是介于0和1之间的常数。 希尔排序 4线性阶(O(n))排序 基数排序此外还有桶、箱排序。 说明 1当原表有序或基本有序时直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数时间复杂度可降至On 2而快速排序则相反当原表基本有序时将蜕化为冒泡排序时间复杂度提高为On2 3原表是否有序对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性 排序算法的稳定性:若待排序的序列中存在多个具有相同关键字的记录经过排序 这些记录的相对次序保持不变则称该算法是稳定的若经排序后记录的相对 次序发生了改变则称该算法是不稳定的。 稳定性的好处排序算法如果是稳定的那么从一个键上排序然后再从另一个键上排序第一个键排序的结果可以为第二个键排序所用。基数排序就是这样先按低位排序逐次按高位排序低位相同的元素其顺序再高位也相同时是不会改变的。另外如果排序算法稳定可以避免多余的比较。 稳定的排序算法冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法选择排序、快速排序、希尔排序、堆排序。 选择排序算法的准则 每种排序算法都各有优缺点。因此在实用时需根据不同情况适当选用甚至可以将多种方法结合起来使用。 选择排序算法的依据 影响排序的因素有很多平均时间复杂度低的算法并不一定就是最优的。相反有时平均时间复杂度高的算法可能更适合某些特殊情况。同时选择算法时还得考虑它的可读性以利于软件的维护。一般而言需要考虑的因素有以下四点 1、待排序的记录数目n的大小 2、记录本身数据量的大小也就是记录中除关键字外的其他信息量的大小 3、关键字的结构及其分布情况 4、对排序稳定性的要求。 设待排序元素的个数为n。 1当n较大则应采用时间复杂度为O(nlog2n)的排序方法快速排序、堆排序或归并排序序。 快速排序是目前基于比较的内部排序中被认为是最好的方法当待排序的关键字是随机分布时快速排序的平均时间最短 堆排序如果内存空间允许且要求稳定性的 归并排序它有一定数量的数据移动所以我们可能过与插入排序组合先获得一定长度的序列然后再合并在效率上将有所提高。 2当n较大内存空间允许且要求稳定性 》归并排序 3当n较小可采用直接插入或直接选择排序。 直接插入排序当元素分布有序直接插入排序将大大减少比较次数和移动记录的次数。 直接选择排序元素分布有序如果不要求稳定性选择直接选择排序 5一般不使用或不直接使用传统的冒泡排序。 6基数排序 基数排序是一种稳定的排序算法但有一定的局限性 1、关键字可分解。 2、记录的关键字位数较少如果密集更好 3、如果是数字时最好是无符号的否则将增加相应的映射复杂度可先将其正负分开排序。
