设计师一般用什么网站,怎么写代码自己制作网站,长沙市住房和城乡建设局网站,wordpress无法进入admin前言
算法和数据结构是一个程序员的内功#xff0c;所以经常在一些笔试中都会要求手写一些简单的排序算法#xff0c;以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法#xff0c;一起学习一下。
一、冒泡排序
思路#xff1a;
比较相邻的元素。如果第一…前言
算法和数据结构是一个程序员的内功所以经常在一些笔试中都会要求手写一些简单的排序算法以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法一起学习一下。
一、冒泡排序
思路
比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素就是最大的数排除最大的数接着下一轮继续相同的操作确定第二大的数...重复步骤1-3直到排序完成。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name BubbleSort* date 2020-09-05 21:38**/
public class BubbleSort extends BaseSort {public static void main(String[] args) {BubbleSort sort new BubbleSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}for (int i 0; i nums.length - 1; i) {for (int j 0; j nums.length - i - 1; j) {if (nums[j] nums[j 1]) {int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}}
}
//10万个数的数组耗时21554毫秒
平均时间复杂度O(n²)
空间复杂度O(1)
算法稳定性稳定
二、插入排序
思路
从第一个元素开始该元素可以认为已经被排序取出下一个元素在前面已排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name InsertSort* date 2020-09-05 22:34**/
public class InsertSort extends BaseSort {public static void main(String[] args) {BaseSort sort new InsertSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}for (int i 0; i nums.length - 1; i) {//当前值int curr nums[i 1];//上一个数的指针int preIndex i;//在数组中找到一个比当前遍历的数小的第一个数while (preIndex 0 curr nums[preIndex]) {//把比当前遍历的数大的数字往后移动nums[preIndex 1] nums[preIndex];//需要插入的数的下标往前移动preIndex--;}//插入到这个数的后面nums[preIndex 1] curr;}}
}
//10万个数的数组耗时2051毫秒
平均时间复杂度O(n²)
空间复杂度O(1)
算法稳定性稳定
三、选择排序
思路
第一轮找到最小的元素和数组第一个数交换位置。
第二轮找到第二小的元素和数组第二个数交换位置...
直到最后一个元素排序完成。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name SelectSort* date 2020-09-06 22:27**/
public class SelectSort extends BaseSort {public static void main(String[] args) {SelectSort sort new SelectSort();sort.printNums();}Overrideprotected void sort(int[] nums) {for (int i 0; i nums.length; i) {int minIndex i;for (int j i 1; j nums.length; j) {if (nums[j] nums[minIndex]) {minIndex j;}}if (minIndex ! i) {int temp nums[i];nums[minIndex] temp;nums[i] nums[minIndex];}}}
}
//10万个数的数组耗时8492毫秒
算法复杂度O(n²) 算法空间复杂度O(1) 算法稳定性不稳定
四、希尔排序
思路
把数组分割成若干(h)个小组(一般数组长度length/2)然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小h/2-h/4-h/8并且进行排序保证有序。当h1时则数组排序完成。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name SelectSort* date 2020-09-06 22:27**/
public class ShellSort extends BaseSort {public static void main(String[] args) {ShellSort sort new ShellSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}int length nums.length;int temp;//步长int gap length / 2;while (gap 0) {for (int i gap; i length; i) {temp nums[i];int preIndex i - gap;while (preIndex 0 nums[preIndex] temp) {nums[preIndex gap] nums[preIndex];preIndex - gap;}nums[preIndex gap] temp;}gap / 2;}}
}
//10万个数的数组耗时261毫秒
算法复杂度O(nlog2n) 算法空间复杂度O(1) 算法稳定性稳定
五、快速排序
快排面试最喜欢问的排序算法。这是运用分治法的一种排序算法。
思路
从数组中选一个数做为基准值一般选第一个数或者最后一个数。采用双指针(头尾两端)遍历从左往右找到比基准值大的第一个数从右往左找到比基准值小的第一个数交换两数位置直到头尾指针相等或头指针大于尾指针把基准值与头指针的数交换。这样一轮之后左边的数就比基准值小右边的数就比基准值大。对左边的数列重复上面12步骤。对右边重复12步骤。左右两边数列递归结束后排序完成。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name SelectSort* date 2020-09-06 22:27**/
public class QuickSort extends BaseSort {public static void main(String[] args) {QuickSort sort new QuickSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}quickSort(nums, 0, nums.length - 1);}private void quickSort(int[] nums, int star, int end) {if (star end) {return;}int i star;int j end;int key nums[star];while (i j) {while (i j nums[j] key) {j--;}while (i j nums[i] key) {i;}if (i j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}}nums[star] nums[i];nums[i] key;quickSort(nums, star, i - 1);quickSort(nums, i 1, end);}
}
//10万个数的数组耗时50毫秒
算法复杂度O(nlogn) 算法空间复杂度O(1) 算法稳定性不稳定
六、归并排序
归并排序是采用分治法的典型应用而且是一种稳定的排序方式不过需要使用到额外的空间。
思路
把数组不断划分成子序列划成长度只有2或者1的子序列。然后利用临时数组对子序列进行排序合并再把临时数组的值复制回原数组。反复操作1~2步骤直到排序完成。
归并排序的优点在于最好情况和最坏的情况的时间复杂度都是O(nlogn)所以是比较稳定的排序方式。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name MergeSort* date 2020-09-08 23:30**/
public class MergeSort extends BaseSort {public static void main(String[] args) {MergeSort sort new MergeSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}//归并排序mergeSort(0, nums.length - 1, nums, new int[nums.length]);}private void mergeSort(int star, int end, int[] nums, int[] temp) {//递归终止条件if (star end) {return;}int mid star (end - star) / 2;//左边进行归并排序mergeSort(star, mid, nums, temp);//右边进行归并排序mergeSort(mid 1, end, nums, temp);//合并左右merge(star, end, mid, nums, temp);}private void merge(int star, int end, int mid, int[] nums, int[] temp) {int index 0;int i star;int j mid 1;while (i mid j end) {if (nums[i] nums[j]) {temp[index] nums[j];} else {temp[index] nums[i];}}while (i mid) {temp[index] nums[i];}while (j end) {temp[index] nums[j];}//把临时数组中已排序的数复制到nums数组中if (index 0) System.arraycopy(temp, 0, nums, star, index);}
}
//10万个数的数组耗时26毫秒
算法复杂度O(nlogn) 算法空间复杂度O(n) 算法稳定性稳定
七、堆排序
大顶堆概念每个节点的值都大于或者等于它的左右子节点的值所以顶点的数就是最大值。 思路
对原数组构建成大顶堆。交换头尾值尾指针索引减一固定最大值。重新构建大顶堆。重复步骤2~3直到最后一个元素排序完成。
构建大顶堆的思路可以看代码注释。
动画演示 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name HeapSort* date 2020-09-08 23:34**/
public class HeapSort extends BaseSort {public static void main(String[] args) {HeapSort sort new HeapSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}heapSort(nums);}private void heapSort(int[] nums) {if (nums null || nums.length 2) {return;}//构建大根堆createTopHeap(nums);int size nums.length;while (size 1) {//大根堆的交换头尾值固定最大值在末尾swap(nums, 0, size - 1);//末尾的索引值往左减1size--;//重新构建大根堆updateHeap(nums, size);}}private void createTopHeap(int[] nums) {for (int i 0; i nums.length; i) {//当前插入的索引int currIndex i;//父节点的索引int parentIndex (currIndex - 1) / 2;//如果当前遍历的值比父节点大的话就交换值。然后继续往上层比较while (nums[currIndex] nums[parentIndex]) {//交换当前遍历的值与父节点的值swap(nums, currIndex, parentIndex);//把父节点的索引指向当前遍历的索引currIndex parentIndex;//往上计算父节点索引parentIndex (currIndex - 1) / 2;}}}private void updateHeap(int[] nums, int size) {int index 0;//左节点索引int left 2 * index 1;//右节点索引int right 2 * index 2;while (left size) {//最大值的索引int largestIndex;//如果右节点大于左节点则最大值索引指向右子节点索引if (right size nums[left] nums[right]) {largestIndex right;} else {largestIndex left;}//如果父节点大于最大值则把父节点索引指向最大值索引if (nums[index] nums[largestIndex]) {largestIndex index;}//如果父节点索引指向最大值索引证明已经是大根堆退出循环if (largestIndex index) {break;}//如果不是大根堆则交换父节点的值swap(nums, largestIndex, index);//把最大值的索引变成父节点索引index largestIndex;//重新计算左节点索引left 2 * index 1;//重新计算右节点索引right 2 * index 2;}}private void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}
}
//10万个数的数组耗时38毫秒
算法复杂度O(nlogn) 算法空间复杂度O(1) 算法稳定性不稳定
八、桶排序
思路
找出最大值最小值。根据数组的长度创建出若干个桶。遍历数组的元素根据元素的值放入到对应的桶中。对每个桶的元素进行排序(可使用快排插入排序等)。按顺序合并每个桶的元素排序完成。
对于数组中的元素分布均匀的情况排序效率较高。相反的如果分布不均匀则会导致大部分的数落入到同一个桶中使效率降低。
动画演示(来源于五分钟学算法侵删) 实现代码
/*** author Ye Hongzhi 公众号java技术爱好者* name BucketSort* date 2020-09-08 23:37**/
public class BucketSort extends BaseSort {public static void main(String[] args) {BucketSort sort new BucketSort();sort.printNums();}Overrideprotected void sort(int[] nums) {if (nums null || nums.length 2) {return;}bucketSort(nums);}public void bucketSort(int[] nums) {if (nums null || nums.length 2) {return;}//找出最大值最小值int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for (int num : nums) {min Math.min(min, num);max Math.max(max, num);}int length nums.length;//桶的数量int bucketCount (max - min) / length 1;int[][] bucketArrays new int[bucketCount][];//遍历数组放入桶内for (int i 0; i length; i) {//找到桶的下标int index (nums[i] - min) / length;//添加到指定下标的桶里并且使用插入排序排序bucketArrays[index] insertSortArrays(bucketArrays[index], nums[i]);}int k 0;//合并全部桶的for (int[] bucketArray : bucketArrays) {if (bucketArray null || bucketArray.length 0) {continue;}for (int i : bucketArray) {//把值放回到nums数组中nums[k] i;}}}//每个桶使用插入排序进行排序private int[] insertSortArrays(int[] arr, int num) {if (arr null || arr.length 0) {return new int[]{num};}//创建一个temp数组长度是arr数组的长度1int[] temp new int[arr.length 1];//把传进来的arr数组复制到temp数组for (int i 0; i arr.length; i) {temp[i] arr[i];}//找到一个位置插入形成新的有序的数组int i;for (i temp.length - 2; i 0 temp[i] num; i--) {temp[i 1] temp[i];}//插入需要添加的值temp[i 1] num;//返回return temp;}
}
//10万个数的数组耗时8750毫秒
算法复杂度O(MN)
算法空间复杂度O(MN)
算法稳定性稳定(取决于桶内的排序算法这里使用的是插入排序所以是稳定的)。
总结 动画演示来源于算法学习网站https://visualgo.net
讲完这些排序算法后可能有人会问学这些排序算法有什么用呢难道就为了应付笔试面试平时开发也没用得上这些。
我觉得我们应该换个角度来看比如高中时我们学物理化学数学那么多公式定理现在也没怎么用得上但是高中课本为什么要教这些呢
我的理解是第一普及一些常识性的问题。第二锻炼思维提高解决问题的能力。第三为了区分人才。
回到学排序算法有什么用的问题上实际上也一样。这些最基本的排序算法就是一些常识性的问题作为开发者应该了解掌握。同时也锻炼了编程思维其中包含有双指针分治递归等等的思想。最后在面试中体现出来的就是人才的划分懂得这些基本的排序算法当然要比不懂的人要更有竞争力。 原文链接 本文为阿里云原创内容未经允许不得转载。
