做服装最好的网站建设,dede中英文网站,互联网做网站地推,成都网站开发费用数据结构 排序 文章目录 数据结构 排序1. 排序的概念及引用1.1 排序的概念1.2 常见的排序算法 2.常见排序算法的实现2.1 插入排序2.1.1 基本思想2.1.2 直接插入排序2.1.3 希尔排序(缩小增量排序) 2.2 选择排序2.2.1 基本思想2.2.2 直接选择排序2.2.3 堆排序 2.3 交换排序2.3.1 …数据结构 排序 文章目录 数据结构 排序1. 排序的概念及引用1.1 排序的概念1.2 常见的排序算法 2.常见排序算法的实现2.1 插入排序2.1.1 基本思想2.1.2 直接插入排序2.1.3 希尔排序(缩小增量排序) 2.2 选择排序2.2.1 基本思想2.2.2 直接选择排序2.2.3 堆排序 2.3 交换排序2.3.1 基本思想2.3.2 冒泡排序2.3.2 快速排序2.3.3 非递归-快排 2.4 归并排序 3. 排序算法复杂度及稳定性分析4. 其它非基于比较的排序(拓展) 1. 排序的概念及引用
1.1 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小进行递增或递减的排列操作 稳定性: 若两元素相同排序后第一个元素依旧在第二个元素之前则称排序算法是稳定的否则称为不稳定的如图 内部排序: 数据元素全部放在内存中的排序;
外部排序: 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的排序算法 本文将对以上排序算法进行分析
2.常见排序算法的实现
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。实际中我们玩扑克牌时就用了插入排序的思想: 2.1.2 直接插入排序
操作方法:
传入数组arr此时需要插入元素下标设为iarr[i]依次与arr[i-1], arr[i-2]等元素进行比较直到找到合适的插入位置k将(k-i)之间的元素依次往后移动一个位置再将arr[i] 插入到k位置重复上述操作直到i下标遍历结束 代码示例:
/*** 直接插入排序* 时间复杂度最好O(n) 最坏O(n²)* 空间复杂度O(1)* 稳定性稳定* 适用范围基本上趋于有序的序列其越有序速度越快*/
public void insertSort(int[] arr) {for (int i 0;i arr.length;i) {int temp arr[i];int j i - 1;for (;j 0;j--) {if (arr[j] temp) {arr[j1] arr[j];}else {break;}}arr[j1] temp;}}直接插入排序特性
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度最好O(N)最坏O(N²)空间复杂度O(1)稳定性稳定
2.1.3 希尔排序(缩小增量排序)
希尔排序法由称缩小增量法。希尔排序法的基本思想是先选定一个整数(gap)把待排序文件中所有记录分成多个组所有距离相等的分在同一个组内并对每一组内的记录进行排序。然后取原来gap的一半重复上述分组和排序的工作。当gap 1时所有记录已经在统一组内排好序 代码示例: /*** 希尔排序* 是对直接插入排序的优化* param arr*/public void shellSort(int[] arr) {int gap arr.length;while(gap 1) {gap / 2;shell(arr, gap);}}private void shell(int[] arr, int gap) {for (int i gap;i arr.length;i) {int temp arr[i];int j i - gap;for (;j 0;j - gap) {if (arr[j] temp) {arr[jgap] arr[j];}else {break;}}arr[jgap] temp;}}希尔排序特性: 可以认为希尔排序是对直接插入排序的优化 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比 希尔排序的时间复杂度不好计算因为gap的取值方式很多导致很难去计算因此一些书中给出的希尔排序的时间复杂度都不固定: 《数据结构(C语言版)》—严蔚敏 《数据结构–用面向对象方法与C描述》—殷人昆 在这里我们按照O(n^1.25)到O(1.6 * n ^ 1.25)来算 稳定性不稳定
2.2 选择排序
2.2.1 基本思想
每一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完
2.2.2 直接选择排序
在元素集合中选择关键码(下标)最大(或最小)的元素将最小值设置为该下标元素依次与下标后面的元素进行比较将最小值的下标记录下来直到下标遍历到数组最后将此时最小值下标元素与最开始最小值的下标元素进行交换 1380)
代码示例: /*** 直接选择排序* 时间复杂度 O(N²)* 空间复杂度 O(1)* 稳定性不稳定* 适用范围效率不高实际很少使用*/public void selectSort(int[] arr) {for (int i 0;i arr.length;i) {int min i;for (int j i;j arr.length;j) {if (arr[j] arr[min]) {min j;}}swap(arr,min,i);}}private void swap(int[] arr, int x, int y) {int temp arr[x];arr[x] arr[y];arr[y] temp;}直接选择排序性质:
直接选择排序思路容易理解但效率不高实际中很少使用时间复杂度 O(N²)空间复杂度 O(1)稳定性不稳定
在这里我们可以对直接选择排序进行一个优化
/*直接排序优化版*/public void selectSort2(int[] arr) {int left 0;int right arr.length - 1;while(left right) {int minIndex left;int maxIndex left;for (int i left 1;i right;i) {if (arr[i] arr[maxIndex]) {maxIndex i;}if (arr[i] arr[minIndex]) {minIndex i;}}swap(arr,minIndex,left);//此时如果maxIndex与left相等// 需要将maxIndex位置修改为此时的minIndex位置// 因为前面已经将left与minIndex位置的元素进行了交换if (maxIndex left) {maxIndex minIndex;}swap(arr,maxIndex,right);left;right--;}}2.2.3 堆排序
堆排序在之前的文章堆的应用中有举例过这里再复习一下
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据的需要注意的是排升序要建大堆排降序建小堆 代码示例: /*** 堆排序* 1. 堆排序使用堆来选数效率高了很多* 2. 时间复杂度O(N*log₂N)* 3. 空间复杂度O(1)* 4. 稳定性不稳定* param arr*/public void heapSort(int[] arr) {createHeap(arr);int end arr.length - 1;while(end 0) {swap(arr, 0, end);shiftBigDown(arr, 0, end);end--;}}public void createHeap(int[] array) {for (int parent (array.length - 1 - 1)/2;parent 0;parent--) {shiftBigDown(array,parent,array.length);}}public void shiftBigDown(int[] elem, int parent,int len) {//左孩子int child 2 * parent 1;while(child len) {//判断是否存在右孩子 且右孩子和左孩子哪个更大大的为childif (child1 len elem[child1] elem[child]) {child;}//判断根节点和child的大小若根节点大则结束遍历否则交换两个节点if (elem[child] elem[parent]) {swap(elem, child, parent);parent child;child 2 * parent 1;}else {break;}}}堆排序特性:
堆排序使用堆来选数效率高了很多时间复杂度O(N*log₂N)空间复杂度O(1)稳定性不稳定
2.3 交换排序
2.3.1 基本思想
所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动
2.3.2 冒泡排序
在写数组的时候有介绍过冒泡这里再来复习一下
以升序为例
将数组中相邻元素从前往后依次进行比较如果前一个元素比后一个元素大则交换一趟下来后最大元素就在数组的末尾依次重复上述过程直到数组中所有的元素都排列好 代码示例:
/*** 冒泡排序* 1. 容易理解优化后效率高* 2. 时间复杂度O(N²) 优化后最好情况可达O(N)* 3. 空间复杂度O(1)* 4. 稳定性稳定*/public void bubbleSort(int[] arr) {for (int i 0;i arr.length;i) {boolean flg false;for (int j 0;j arr.length - i - 1;j) {//如果走完一圈后发现没有交换过说明整个数组元素已经有序后面直接退出循环if (arr[j1] arr[j]) {swap(arr,j,j1);flg true;}}if (!flg) {break;}}}冒泡排序特性:
容易理解优化后效率高时间复杂度O(N²) 优化后最好情况可达O(N)空间复杂度O(1)稳定性稳定
2.3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复(利用递归)该过程直到所有元素都排列在相应位置上为止
主框架代码示例: //假设按照升序对arr数组中[left,right)区间的元素进行排序public void quickSort(int[] arr, int left, int right) {if (left right) {return;}//按照基准值对arr数组的[left,right)区间中的元素进行划分int div partitionHoare(arr, left, right);//划分成功后以div为边界形成了左右两部分[left,div)和[div,right)//递归排[left,div)quickSort(arr, left, div);//递归排[div1,right)quickSort(arr, div 1, right);}将区间按照基准值划分为左右两半部分的常见方式有: Hoare版 代码示例: /*Hoare法*/
public int partitionHoare(int[] arr, int left, int right) {int i left;int j right;int pivot left;while(i j) {while(i j arr[j] arr[pivot]) {j--;}while(i j arr[i] arr[pivot]) {i;}swap(arr, i, j);}swap(arr, i, pivot);return i;}挖坑法 基本思路 先选取一个基准值(这里我们设置第一个数为基准值)选出来后认为此位置为空(坑)从右遍历直到找到小于该基准值的元素然后将该元素填到前面的坑同时此位置变为空(坑)从左遍历直到找到大于该基准值的元素然后将该元素填到前面的坑同时此位置变为空(坑)若左右指针未相遇重复上述23操作当左右指针相遇时将相遇位置的值修改为基准值 代码示例: /*挖坑法*/public int partition(int[] arr, int left, int right) {int i left;int j right;int pivot left;while(i j) {while(i j arr[j] arr[pivot]) {j--;}arr[i] arr[j]; //将j位置的元素赋给i位置此时虽然有两个相同的但j位置的元素可以相当于空while(i j arr[i] arr[pivot]) {i;}arr[j] arr[i]; //将i位置的元素}swap(arr, pivot, i);return i;}前后指针法: 基本思路: 先选取一个基准值(这里我们设置第一个数为基准值)设置两个指针prev和curprev从左边第一个值开始cur开始为prev1若cur此时小于基准值则prev,并且判断prev后是否等于此时的cur若不等于交换cur与prev每次判断完都要移动cur(cur)直到cur最后一个下标则交换prev和基准值然后将此时prev的位置返回 代码示例: /*前后指针法*/public int partition2(int[] arr, int left, int right) {int pivot left; //基准值int prev left;int cur left 1;while(cur right) {if (arr[cur] arr[pivot] arr[prev] ! arr[cur]) {swap(arr,prev,cur);}cur;}swap(arr,pivot,prev);return prev;}2.3.3 非递归-快排
非递归方式版本的快速排序 /*非递归-快排*/public void quickSortNor(int[] arr) {int start 0;int end arr.length - 1;StackInteger stack new Stack();int pivot partitionHoare(arr, start, end);if (pivot - 1 start) {stack.push(start);stack.push(pivot-1);}if (pivot 1 end) {stack.push(pivot1);stack.push(end);}while(!stack.isEmpty()) {end stack.pop();start stack.pop();pivot partitionHoare(arr, start, end);if (pivot - 1 start) {stack.push(start);stack.push(pivot-1);}if (pivot 1 end) {stack.push(pivot1);stack.push(end);}}}快排特性:
快速排序整体的综合性能和使用场景都是比较好的时间复杂度O(N*log₂N)空间复杂度O(log₂N)稳定性不稳定
2.4 归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。做法就是将已有序的子序列合并从而得到完全有序的序列即先使每个子序列有序再使子序列段之间有序。若将两个有序表合并成一个有序表称为二路归并: 代码示例:
/*** 归并排序*/public void mergeSort(int[] arr) {mergeSortFun(arr, 0, arr.length - 1);}private void mergeSortFun(int[] arr, int start, int end) {if (start end) {return;}int mid (start end) / 2;mergeSortFun(arr, start, mid);mergeSortFun(arr, mid 1, end);//合并merge(arr, start, mid, end);}private void merge(int[] arr, int left, int mid, int right) {int s1 left; //数组一起始位置int e1 mid; //数组一结束位置int s2 mid 1; //数组二起始位置int e2 right; //数组二结束位置// 定义一个新的数组int[] newArr new int[right-left1];int k 0; //新数组下标while(s1 e1 s2 e2) {if (arr[s1] arr[s2]) {newArr[k] arr[s1]; //赋完值后两个下标都要往后走}else {newArr[k] arr[s2];}}//其中一个数组走完了将另一个数组所有的值都赋到新的数组while(s1 e1) {newArr[k] arr[s1];}while(s2 e2) {newArr[k] arr[s2];}//将传入数组转换为新数组for (int i 0;i newArr.length;i) {arr[i left] newArr[i];}}归并排序特性:
归并排序的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题时间复杂度O(N*log₂N)空间复杂度O(N)稳定性稳定
拓展: 外部排序排序过程需要在磁盘等外部存储进行的排序 前提内存只有1G需要排序的数据有100G 因为内存中无法把所有的数据全部放下所有需要外部排序而归并排序是最常用的外部排序 先把文件切分成200份每个512M分别对512M排序因为内存已经可以放的下所有任意排序方式都可以进行二路归并同时对200分有序文件做归并过程最终结果就有序了
3. 排序算法复杂度及稳定性分析 排序方法最好平均最坏空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定希尔排序O(n)O(n^1.3)O(n^2)O(1)不稳定堆排序O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定快速排序O(n * log(n))O(n * log(n))O(n^2)O(log(n)) ~ O(n)不稳定归并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定
4. 其它非基于比较的排序(拓展)
我们这里拓展一个排序算法-计数排序
基本思想计数排序又称鸽巢原理是对哈希直接定址法的变形应用。操作步骤
统计相同元素出现的次数根据统计的结果将序列回收到原来的序列中 代码示例:
/*** 计数排序* 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限* 2. 时间复杂度O(MAX(N,范围))* 3. 空间复杂度O(范围)* 4. 稳定性稳定*/public void countSort(int[] arr) {int minVal arr[0];int maxVal arr[0];for (int i 0;i arr.length;i) {//找到数组最大值和最小值用来求新数组长度if (arr[i] maxVal) {maxVal arr[i];}if (arr[i] minVal) {minVal arr[i];}}// 确定计数数组长度int len maxVal - minVal 1;int[] count new int[len];// 遍历arr数组把arr数组中出现元素的次数记录在计数数组中for (int i 0;i arr.length;i) {count[arr[i] - minVal];}// 此时计数数组已经存放了每个数据出现的次数// 遍历计数组把实际的数据写回arr数组int index 0;for (int j 0;j count.length;j) {while(count[j] 0) {arr[index] minVal j;index;count[j]--;}}}计数排序特性:
计数排序在数据范围集中时效率很高但是适用范围及场景有限时间复杂度O(MAX(N,范围))空间复杂度O(范围)稳定性稳定
