网站开发的需求分析论文,科技网站实例,水处理网站源码,做网站的收入来源【Java数据结构】排序 一、排序1.1 排序的概念1.2 排序的稳定性1.3 内部排序和外部排序1.3.1 内部排序1.3.2 外部排序 二、插入排序2.1 直接插入排序2.2 希尔排序 三、选择排序3.1 选择排序3.2 堆排序 四、交换排序4.1 冒泡排序4.2 快速排序Hoare法#xff1a;挖坑法#xff… 【Java数据结构】排序 一、排序1.1 排序的概念1.2 排序的稳定性1.3 内部排序和外部排序1.3.1 内部排序1.3.2 外部排序 二、插入排序2.1 直接插入排序2.2 希尔排序 三、选择排序3.1 选择排序3.2 堆排序 四、交换排序4.1 冒泡排序4.2 快速排序Hoare法挖坑法前后指针 4.3 快速排序的优化4.3.1 三数取中法4.3.2 递归到小的子区间时使用直接插入排序 4.4 非递归快速排序 五、归并排序5.1 递归归并排序5.2 非递归归并排序 六、总结 博客最后附有整篇博客的全部代码 一、排序
1.1 排序的概念 排序是计算机科学中一个非常基础且重要的概念它指的是将一组对象按照某种顺序排列的过程。排序算法是实现排序功能的具体方法通过对数据进行比较、交换或移动等操作使数据元素按照指定的顺序排列。 1.2 排序的稳定性 稳定性是一个重要的概念它描述了排序算法是否能够保持相同元素的相对顺序不变。 排序稳定性 一个排序算法是稳定的如果在排序过程中两个具有相同键值或值的元素在排序前后的相对顺序保持不变。换句话说如果元素A和B在排序前满足A在B之前并且它们的键值相同那么排序后A仍然在B之前。
例如 下面一组数据里面有两个相同的值‘8’为了展现它们的相对位置我们将两个相同值的‘8’用不同元素表示出来。在排序之前‘8’
1.3 内部排序和外部排序
1.3.1 内部排序
内部排序是指在排序过程中所有待排序的数据都能同时存储在内存中进行处理。由于内存访问速度较快内部排序通常效率较高但受限于内存容量适用于数据量较小的场景。 特点 存储所有数据存储在内存中。 效率通常较快因为内存访问速度快。 适用场景数据量较小通常在几万甚至几十万以内。 1.3.2 外部排序
外部排序是指待排序的数据量过大无法全部加载到内存中需要借助外存如磁盘来完成排序的过程。外部排序通常涉及将数据分块处理排序后再合并。 特点 存储数据主要存储在外存如磁盘内存仅用于存储部分数据。 效率通常较慢因为外存访问速度远低于内存。 适用场景数据量巨大如数百万甚至数十亿条记录无法全部加载到内存中。 二、插入排序
2.1 直接插入排序
思想 将待排序的元素逐个插入到已经排好序的序列中从而逐步扩展有序序列的长度直到所有元素都被插入整个序列变为有序。 时间复杂度O(N^2)。 空间复杂度O(1)。 稳定性稳定。
代码: public void insertSort(int[] array){int tmp0;for(int i1;iarray.length-1;i){tmparray[i];int ji-1;for(;j0;j--){if(tmparray[j]){array[j1]array[j];}else{break;}}array[j1]tmp;}}2.2 希尔排序
思想 希尔排序Shell Sort是插入排序的一种改进版本通过将数组分成多个子序列进行排序逐步缩小子序列的间隔增量最终使整个数组有序。 其核心思想如下 选择增量序列初始增量通常为数组长度的一半随后逐步减小直到增量为1。 分组排序按照当前增量将数组分成多个子序列对每个子序列进行插入排序。 逐步缩小增量重复上述过程直到整个数组基本有序最后使用增量为1的插入排序完成最终排序。 时间复杂度O(n^1.3 )至 O( n^1.5)之间。 空间复杂度O(1)。 稳定性不稳定。
代码 public void shellSort(int[] array){int gaparray.length;while(gap1){gapgap/2;shell(array,gap);}}private void shell(int[] array, int gap) {int tmp0;for (int i gap; i array.length ; i) {tmparray[i];int ji-gap;for(;j0;j-gap){if(tmparray[j]){array[jgap]array[j];}else{break;}}array[jgap]tmp;}}
三、选择排序
3.1 选择排序
思想 选择排序是一种简单直观的排序算法。它的核心思想是 每次从未排序的部分中选择最小或最大的元素并将其放到已排序部分的末尾。重复上述过程直到所有元素都被排序。 时间复杂度O(N^2)。 空间复杂度O(1)。 稳定性不稳定。
代码 public void selectSort(int[] array){int minIndex0;for (int i0;iarray.length;i){minIndexi;for(int ji1;jarray.length;j){if(array[minIndex]array[j]){minIndexj;}}int tmparray[i];array[i]array[minIndex];array[minIndex]tmp;}}延伸 思路 定义两个变量‘minIndex’和‘maxIndex’来接收遍历完一遍数组得到的最大值和最小值下标将得到的最大值和最小值下标分别与这组数组的最左边和最右边的值交换以此类推。 时间复杂度O(n²) 空间复杂度O(1) 稳定性不稳定
代码 public void selectSort2(int[] array) {int left0;int rightarray.length-1;int lenarray.length;while(leftright){int minIndexleft;int maxIndexleft;for (int i left; i len; i) {if(array[i]array[minIndex]){minIndexi;}if(array[i]array[maxIndex]){maxIndexi;}}swap(array,left,minIndex);left;swap(array,right,maxIndex);right--;len--;}}public void swap(int[] array,int x,int y){int tmparray[x];array[x]array[y];array[y]tmp;}3.2 堆排序
思路 建立大根堆将大根堆的堆顶元素和最后一个元素进行交换交换完后将剩下的堆重新调整以此类推。 时间复杂度O(N*logN)。 空间复杂度O(1)。 稳定性不稳定。
代码
public void heapSort(int[] array){//创建堆createHeap(array);int endarray.length-1;while(end0){swap(array,0,end);shiftDown(array,0,end);end--;}}public void createHeap(int[] array){for(int parent(array.length-1-1)/2;parent0;parent--){shiftDown(array,parent,array.length);}}public void shiftDown(int[] array,int parent,int length){int child parent*21;while(childlength){//如果孩子存在找到左右孩子中较小的孩子用child标记if (child 1 length array[child] array[child1]) {child;}if(array[parent]array[child]){swap(array,parent,child);parentchild;childparent*21;}else{break;}}}四、交换排序
4.1 冒泡排序
思想 核心思想是通过相邻元素之间的比较和交换逐步将最大或最小的元素“冒泡”到数组的末尾或开头。这个过程重复进行直到整个数组有序。 时间复杂度O(N^2) 。 空间复杂度O(1)。 稳定性稳定。
代码
public void bubbleSort(int[] array){boolean flagtrue;for (int i 0; i array.length-1; i) {for (int j 0;jarray.length-1-i;j ){if(array[j]array[j1]){swap(array,j,j1);flagfalse;}}if(flag){break;}}}4.2 快速排序
思想 核心思想是通过分区操作将数组分为两部分使得一部分的所有元素都小于或等于另一部分的所有元素然后递归地对这两部分进行排序。 时间复杂度O(N*logN)至O(n^2)。 空间复杂度O(logN)至O(N)。 稳定性不稳定。
Hoare法
思路 选定序列第一个为基准从后边往前找到比基准小的停下来从前边找到比基准大的停下来交换直到左右相遇相遇下标的值与基准交换。 代码: public void quickSort(int[] array){hoareSort(array,0,array.length-1);}public void hoareSort(int[] array,int start,int end) {if(startend){return;}int pivot partition(array, start, end);hoareSort(array,start,pivot-1);hoareSort(array,pivot1,end);}private int partition(int[] array, int left, int right) {int flagleft;while(leftright){while(leftrightarray[right]array[flag]){right--;}while(leftrightarray[left]array[flag]){left;}swap(array,left,right);}swap(array,left,flag);return left;}挖坑法
思路 选定序列第一个为基准从后往前找找到小于基准的将其放到基准的位置接下来从前往后找找到比基准大的放到先前后面找到的比基准小的位置以此类推。 代码 private int partition2(int[] array, int left, int right) {int flagarray[left];while(leftright){while(leftrightarray[right]flag){right--;}array[left]array[right];while(leftrightarray[left]flag){left;}array[right]array[left];}array[left]flag;return left;}前后指针
思路 选定序列第一个为基准定义两个prev和cur来标记下标遍历序列满足cur下标的值小于基准并且prev下标和cur下标不在同一个下标交换prev和cur下标的值如果不满足条件cur。 代码 private int partition3(int[] array, int left, int right) {int prevleft;int curprev1;while(curright){if(array[cur]array[left]array[prev]!array[cur]){swap(array,prev,cur);}cur;}swap(array,prev,left);return prev;}4.3 快速排序的优化
4.3.1 三数取中法
优点 优化性能通过选择中值作为基准值减少了因数据分布不均匀而导致的性能退化。 提高稳定性在处理接近有序或完全逆序的数据时性能更加稳定。 代码 public void hoareSort(int[] array,int start,int end) {if(startend){return;}int midIndexgetNumber(array,start,end);swap(array,start,midIndex);int pivot partition(array, start, end);hoareSort(array,start,pivot-1);hoareSort(array,pivot1,end);}private int getNumber(int[] array,int left,int right){int mid(leftright)/2;if(array[left]array[right]){if(array[mid]array[left]){return left;} else if (array[mid]array[right]) {return right;}else{return mid;}}else{if(array[mid]array[right]){return right;} else if (array[mid]array[left]) {return left;}else{return mid;}}}
4.3.2 递归到小的子区间时使用直接插入排序
优点 因为直接插入排序的特点就是越有序越快。 代码 public void hoareSort(int[] array,int start,int end) {if(startend){return;}
// int midIndexgetNumber(array,start,end);
// swap(array,start,midIndex);if (end - start1 10) {insertSortRange(array,start,end);return;}int pivot partition(array, start, end);hoareSort(array,start,pivot-1);hoareSort(array,pivot1,end);}private void insertSortRange(int[] array, int start, int end) {int tmp0;for(int istart1;iend;i){tmparray[i];int ji-1;for(;jstart;j--){if(tmparray[j]){array[j1]array[j];}else{break;}}array[j1]tmp;}}4.4 非递归快速排序
思想 通过挖坑法先求得基准下标通过基准下标将基准左右两边序列的start和end存进栈中存入栈中的先后顺序要一致通过pop弹出start和end再通过挖坑法求得基准下标以此类推当栈为空则证明已经排序好了 代码 public void quickNor(int[] array,int start,int end) {StackInteger stacknew Stack();int pivot partition2(array, start, end);if(pivotstart1){stack.push(start);stack.push(pivot-1);}if(pivotend-1){stack.push(pivot1);stack.push(end);}while(!stack.isEmpty()){endstack.pop();startstack.pop();pivotpartition2(array, start, end);if(pivotstart1){stack.push(start);stack.push(pivot-1);}if(pivotend-1){stack.push(pivot1);stack.push(end);}}}五、归并排序
5.1 递归归并排序
思路 归并排序是一种分治排序算法其核心思想是将数组分成多个小部分分别对这些小部分进行排序然后逐步合并这些有序部分最终得到一个完全有序的数组。 时间复杂度O(N*logN)。 空间复杂度O(N)。 稳定性稳定。
代码: public void mergeSort(int[] nums) {mergeSortSplit(nums, 0, nums.length - 1);}private void mergeSortSplit(int[] nums, int left, int right) {if (left right) {return;}//分解int mid (left right) / 2;mergeSortSplit(nums, left, mid-1);mergeSortSplit(nums, mid 1, right);//合并merge(nums, left, mid, right);}private void merge(int[] nums, int left, int mid, int right) {int[] tmp new int[right - left 1];int k0;int s1left;int s2mid 1;while(s1mids2right){if(nums[s1]nums[s2]){tmp[k]nums[s1];}else{tmp[k]nums[s2];}}while(s1mid){tmp[k]nums[s1];}while(s2right){tmp[k]nums[s2];}for(int ileft; ik; i){nums[i]tmp[i];}}5.2 非递归归并排序 public void mergeSortNor(int[] array){int gap1;while(gaparray.length){for(int i0;iarray.length;iigap*2){int lefti;int midleftgap-1;if(midarray.length){midarray.length-1;}int rightmidgap;if(rightarray.length){rightarray.length-1;}merge(array,left,mid,right);}gap*2;}}六、总结 此篇博客的全部代码
