腾讯云如何创建网站,购物网站的详细设计,最好的网站建设价格,网页设计与制作首页文章目录 十大排序算法选择排序冒泡排序插入排序希尔排序快速排序归并排序堆排序计数排序基数排序桶排序时间复杂度 参考资料 十大排序算法
选择排序 原理 从待排序的数据元素中找出最小或最大的一个元素#xff0c;存放在序列的起始位置#xff0c; 然后再从剩余的未排序元… 文章目录 十大排序算法选择排序冒泡排序插入排序希尔排序快速排序归并排序堆排序计数排序基数排序桶排序时间复杂度 参考资料 十大排序算法
选择排序 原理 从待排序的数据元素中找出最小或最大的一个元素存放在序列的起始位置 然后再从剩余的未排序元素中寻找最小/最大元素放在已排序的序列的末尾 以此类推直到全部待排序的数据元素的个数为零。 实现方法
设置下标指针i和ji从数组的第一个元素开始j从i1个元素开始j遍历到lens选出最小的值min将nums[i]与min交换如果没有找到一个nums[j]nums[i],说明自己本身就是最值不交换i开始选取下一个元素重复2直到i到达lens-1出 以数据{12864518}为例 图示 代码实现
public class Sort {public static void main(String[] args) {int[] nums {12,8,6,45,18};//选择排序selectSort(nums);}public static void selectSort(int[] nums){int lens nums.length;int temp;//优化排序之前先遍历boolean isSort true;for(int i0; i lens-1; i){if(nums[i] nums[i1]){//有无序的isSort false;break;}}if(isSort){return;//直接结束}//优化结束System.out.println(开始选择排序);for(int i0; i lens-1; i){for(int ji1;j lens;j){if(nums[j] nums[i]){temp nums[j];nums[j] nums[i];nums[i] temp;}}}for(int i 0; i lens; i){System.out.print(nums[i] );}}}冒泡排序 原理 通过对排序序列从前向后从下标较小的元素开始依次比较相邻元素的值若发现逆序则交换 使得值比较大的元素逐渐从前向后移动就像水底下的气泡一样逐渐向上冒。 实现方法
设置下标指针i和ji用于统计外循环的次数j用来表示当前轮次需要遍历的元素范围j的范围是0~lens-1-i因为我们这里是每次将最大的值放在尾部因此到第i轮的时候最后i个值已经排完序了不需要再判断了如果nums[j] nums[j1],则进行交换重复上述步骤直到lens轮排序完毕 图示 代码
public class Sort {public static void main(String[] args) {int[] nums {12,8,6,45,18};//冒泡排序bubbleSort(nums);}public static void bubbleSort(int[] nums){int lens nums.length;int temp;System.out.println(开始冒泡排序);for(int i0; i lens - 1; i){for(int j 0; j lens - 1 - i; j){if(nums[j] nums[j 1]){temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}for(int i0;ilens;i){System.out.print(nums[i] );}}
}
插入排序 原理 将一个记录插入到有序表中从而形成一个新的有序表 每一步将一个待排序的元素按照排序码的大小插入到前面已经排好序的一组元素的适当位置上去直到元素全部插入为主。 实现过程
每次从待排序数组中选取元素value将其插入到有序表中设置下标指针i和ji指向待排序元素j指向已排序元素尾部并不断左移ji-1,当j不越界并且value小于nums[j]的时候我们要将nums[j]及其后面的数组往右边移一位直到value大于等于nums[j]此时j1的位置是value应该插入的位置将其插入进去即可 图示 代码
public class Sort {public static void main(String[] args) {int[] nums {12, 8, 6, 45, 18};insertSort(nums);}public static void insertSort(int[] nums) {int lens nums.length;System.out.println(开始插入排序);for (int i 1; i lens; i) {int value nums[i];int j;for (j i - 1; j 0 value nums[j]; j--) {nums[j 1] nums[j];//挪空位}nums[j 1] value;}for (int i 0; i lens; i) {System.out.print(nums[i] );}}
}希尔排序 原理 先将整个待排序的记录序列分组对若干子序列分别进行直接插入排序 随着增量逐渐减少即整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序。 实现过程 参考java希尔排序 代码
public class Sort {public static void main(String[] args) {int[] nums {12, 8, 6, 45, 18};shellSort(nums);}public static void shellSort(int[] nums) {for (int gap nums.length / 2; gap 0; gap / 2) {for (int i gap; i nums.length; i) {for (int j i - gap; j 0; j - gap) {if (nums[j] nums[j gap]) {int temp nums[j];nums[j] nums[j gap];nums[j gap] temp;}}}}System.out.println(Arrays.toString(nums));}
}快速排序 原理 通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小 然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 图示 代码
public class Sort {static int[] nums {12, 8, 6, 45, 18};public static void main(String[] args) {quickSort(nums, 0, nums.length - 1);System.out.println(快速排序 Arrays.toString(nums));}public static void quickSort(int[] nums, int low, int high) {int i, j, pivot;//结束条件if (low high) {return;}i low;j high;//选择的节点默认选择第一位数pivot nums[low];while (i j) {//从右到左找到第一个比pivot小的数while (nums[j] pivot i j) {j--;}//从左到右找到比节点大的数while (nums[i] pivot i j) {i;}if (i j) {//循环找到后交换int temp nums[i];nums[i] nums[j];nums[j] temp;}}//一轮结束后交换节点的数和ij相遇点的数nums[low] nums[i];nums[i] pivot;//对pivot左边和右边的数进行快速排序quickSort(nums, low, i - 1);quickSort(nums, i 1, high);}
}归并排序 原理 基于分治思想先将待排序的数组不断拆分直到拆分到区间里只剩下一个元素的时候。 不断合并两个有序的子区间直到所有区间都合并在一起此时数组有序。 实现过程
编写递归函数sortMerge(int[] nums,int left,int right);参数nums表示要排序的数组left和right表示当前排序的范围每进入一个子函数计算mid将待排序数组再一分为二函数sortMerge的终止条件是leftright即无法再拆分回溯时要合并刚刚自己拆分的两个数组合并的范围同样是left到right用k表示合并后数组元素对应的下标此时两个子区间的合并就说合并两个有序数组,借助临时数组temp存储还未合并的两个子数组原始的内容有序数组1的下标用i表示范围是[left,mid]有序数组2的下标用j表示范围是[mid1,right]在ij都未越界的情况下选择小的存到nums[k],并将对应的指针往右移若i/j越界则将j/i剩下的数据修改到nums中
图示 从数组中间拆分每次拆成两个子区间
函数的指向过程就是构造一个二叉树红色箭头是当递归到leftright时进行回溯 此时指向函数体里面的合成操作
代码
public class Sort {public static void main(String[] args) {int[] nums {6, 2, 7, 1, 9, 4, 8, 5, 12, 10}; //给定一个数组int len nums.length;int[] temp new int[len];mergeSort(nums, 0, len - 1, temp);System.out.println(Arrays.toString(nums)); //打印输出得到数组}private static void mergeSort(int[] nums, int left, int right, int[] temp) {if (left right) {//当拆分到数组当中只要一个值的时候结束递归return;}int mid (left right) / 2; //找到下次要拆分的中间值mergeSort(nums, left, mid, temp);//记录树左边的mergeSort(nums, mid 1, right, temp);//记录树右边的//合并两个区间for (int i left; i right; i) {temp[i] nums[i];//temp就是辅助列表新列表的需要排序的值就是从辅助列表中拿到的}int i left; //左子数组起点int j mid 1; //右子数组起点//合并两个有序数组成为一个新的有序数组for (int k left; k right; k) {//k 就为当前要插入的位置if (i mid 1) { //i到了右子数组起点证明左子数字已经比较完毕nums[k] temp[j]; //右子数字剩余的全部值赋给原数组j;} else if (j right 1) { //当j超过当前的数组范围证明右区间的数组已经遍历完毕了nums[k] temp[i];//如果k还没有走完证明左区间数据还有剩余直接全部复制上去i;}//用来比较寻找小的哪一位插入else if (temp[i] temp[j]) { //如果左子数组最小值小于右子数组最小值nums[k] temp[i]; //将两个数组中的最小值赋值给原数组i;} else {nums[k] temp[j];j;}}}
}堆排序 原理 堆是一种完全二叉树的数据结构可以分为大根堆小根堆。 大根堆每个结点的值都大于或者等于他的左右孩子结点的值 小根堆每个结点的值都小于或等于其左右孩子的结点值 以大根堆为例首先把待排序的元素按照大小在二叉树位置上排列且要满足堆的特性。 根据特性把根节点拿出来然后再堆化下即用父节点和他的孩子节点进行比较取最大的孩子节点和其进行交换 再把根节点拿出来一直循环到最后一个节点就排序好了。 实现过程
给定的待排序序列作为二叉树的层序遍历结果构建二叉树将这个二叉树构造成一个大顶堆从最后一个非叶子结点开始比较它的左右孩子是否比自己大比自己大就交换逐层往上找最后根节点是最大值将堆顶元素与末尾元素进行交换此时末尾为最大值将剩余n-1个元素重新构成一个堆这样会得到n个元素的次小值。如此反复执行便得到有序序列 图示 代码
public class Sort {static int[] nums {4, 6, 1, 8, 9, 3, 5, 7, 11};public static void main(String[] args) {//给定一个数组heapSort(nums);System.out.println(Arrays.toString(nums)); //打印输出得到数组}public static void heapSort(int[] nums) {System.out.println(开始堆排序);//1.构建堆使得nums[0]成为最大值buildMaxHeap(nums);for (int i nums.length - 1; i 1; i--) {swap(nums, 0, i);//将当前的最大堆顶放在最后一位adjustHeap(nums, 0, i);//寻找次大值}}public static void buildMaxHeap(int[] nums) {for (int i (nums.length - 1 - 1) / 2; i 0; i--) {adjustHeap(nums, i, nums.length);}}public static void adjustHeap(int[] nums, int i, int length) {int left 2 * i 1;int right 2 * i 2;int largest i;if (left length nums[left] nums[i]) {//左结点大修改largest下标largest left;}if (right length nums[right] nums[largest]) {//看右节点的值是否会比largest的大largest right;}if (largest ! i) {//需要交换swap(nums, i, largest);adjustHeap(nums, largest, length);//继续调整}}public static void swap(int[] nums, int i, int largest) {int temp nums[i];nums[i] nums[largest];nums[largest] temp;}
}计数排序 原理 将待排序元素值转换为键存储在额外开辟的数组空间中其要求输入的数据必须是有确定范围的整数。 实现过程 以待排序元素为0~9以内整数为例 我们创建一个长度为10的整数ansans[i]用于统计数字i在待排序元素中出现的次数 之后根据ans[i]的值输出ans[i]次i直到遍历完成。 图示 代码
public class Sort {static int[] nums {6, 2, 7, 1, 9, 4, 8, 5, 2, 1, 3, 2, 4, 4, 5, 6, 7};public static void main(String[] args) {int len nums.length;countSort(nums);System.out.println(Arrays.toString(nums)); //打印输出得到数组}public static void countSort(int[] nums) {System.out.println(开始计数排序);int len nums.length;int[] a new int[10];//下标0~9for (int i 0; i len; i) {a[nums[i]];}int k 0;for (int i 0; i 10; i) {for (int j 1; j a[i]; j) {nums[k] i;}}}
}基数排序
原理 通过键值的部分资讯将要排序的元素分配至某些桶中对于一个整数数组先按个位数从低到高进行排序相同的放在同一个桶中 之后按十位数排序再按百位数排序直到所有数的第k位数都是0K取决于数组中最大的元素。实现过程
找出数组中的最大值maxNum遍历轮次与其有关指针div表示的是当前按哪一个键值进行排序1101001000分别表示键值为个位十位百位千位。每一轮计算元素对应的键值做法是 nums[i] / div % 10; 如nums[i] 248,div 10; nums[i]/div 248 / 10 24,24 %10得到4将元素依次装入对应的桶中每一轮分配完之后将桶中的数据按顺序依次传回原数组nums中因为下一轮遍历需要根据此顺序。 图示 代码
public class Sort {static int[] nums {4, 6, 1, 8, 9, 3, 5, 7, 11};public static void main(String[] args) {//给定一个数组radixSort(nums);System.out.println(Arrays.toString(nums)); //打印输出得到数组}public static void radixSort(int[] nums) {System.out.println(开始基数排序);//先找到最大值知道要排序几轮int maxNum Integer.MIN_VALUE;for (int i 0; i nums.length; i) {if (nums[i] maxNum) {maxNum nums[i];}}//创建10个桶因为桶里面装的数据个数未知所以用数组list优于二维数组LinkedListInteger[] lists new LinkedList[10];for (int i 0; i 10; i) {lists[i] new LinkedList();}//开始分桶,div表示当前排序的位数1为个位10为十位for (int div 1; div maxNum; div * 10) {for (int i 0; i nums.length; i) {int num nums[i] / div % 10;//计算其位数的值lists[num].offer(nums[i]);}//把桶中的数据传回nums数组int index 0;for (LinkedListInteger list : lists) {while (!list.isEmpty()) {nums[index] list.poll();}}}}
}桶排序
原理 将序列中的元素分布到一定数量的桶内然后分别对桶内的元素进行排序与最后再将各个桶内的有序子序列放回原始序列中。 对于桶内的元素可以使用别的排序算法也可以递归使用桶排序 一般桶内元素使用插入算法进行排序。实现过程
找出待排序的数组中的最大元素max和最小元素min根据指定的桶数创建桶本文使用的桶是List结构桶里面的数据也采用List结构存储根据公式遍历数组元素桶编号数组元素-最小值*(桶个数-1)/最大值-最小值把数据放到相同的桶中从小到大遍历每一个桶同时对也桶里的元素进行排序把排好序的元素从索引为0开始放入完成排序
代码
public class Sort {static int[] nums {4, 6, 1, 8, 9, 3, 5, 7, 11};public static void main(String[] args) {//给定一个数组bucketSort(nums, 3);System.out.println(Arrays.toString(nums)); //打印输出得到数组}public static void bucketSort(int[] nums, int bucketSize) {System.out.println(开始桶排序);int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for (int num : nums) {max Math.max(num, max);min Math.min(num, min);}//创建bucketSize个桶ListListInteger bucketList new ArrayList();for (int i 0; i bucketSize; i) {bucketList.add(new ArrayList());}//将数据放入桶中for (int num : nums) {//确定桶号桶编号数组元素-最小值*(桶个数-1)/最大值-最小值int bucketIndex (num - min) * (bucketSize - 1) / (max - min);ListInteger list bucketList.get(bucketIndex);list.add(num);}//对每一个桶进行排序for (int i 0, index 0; i bucketList.size(); i) {ListInteger list bucketList.get(i);list.sort(null);for (int value : list) {nums[index] value;}}}
}时间复杂度
排序方法时间复杂度平均时间复杂度最坏时间复杂度最好)空间复杂度稳定性插入排序O(N2)O(N2)O(N)O(1)稳定希尔排序O(N1.3)O(N2)O(N)O(1)不稳定选择排序O(N2)O(N2)O(N2)O(1)不稳定堆排序O(N log2 N)O(N log2 N)O(N log2 N)O(1)不稳定冒泡排序O(N2)O(N2)O(N)O(1)稳定快速排序O(N log2 N)O(N2)O(N log2 N)O(log2 N)不稳定归并排序O(N log2 N)O(N log2 N)O(N log2 N)O(N)稳定计数排序O(Nk)O(Nk)O(Nk)O(Nk)稳定桶排序O(Nk)O(N2)O(N)O(Nk)稳定基数排序O(N*k)O(N*k)O(N*k)O(Nk)稳定
参考资料
资料1 十大经典排序 快速排序 堆排序 堆排序Java 桶排序
