网站搭建模板,美食网站页面设计源代码,网站不备案可以建设吗,wordpress表情不显示常见算法 1、7种常见排序算法1.1、冒泡排序1.2、简单选择排序1.3、直接插入排序1.4、希尔排序1.5、归并排序1.6、快速排序1.7、堆排序 1、7种常见排序算法
7种常见排序算法的时间复杂度、辅助空间以及稳定性对照表。
排序算法平均情况最好情况最坏情况辅助空间稳定性冒泡排序… 常见算法 1、7种常见排序算法1.1、冒泡排序1.2、简单选择排序1.3、直接插入排序1.4、希尔排序1.5、归并排序1.6、快速排序1.7、堆排序 1、7种常见排序算法
7种常见排序算法的时间复杂度、辅助空间以及稳定性对照表。
排序算法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n^2)O(n)O(n^2)O(1)稳定简单选择排序O(n^2)O(n^2)O()n^2O(1)稳定直接插入排序O(n^2)O(n)O()n^2O(1)稳定希尔排序O(nlogn)~O(n^2)O(n^1.3)O(n^2)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n^2)O(logn)~O(n)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
1.1、冒泡排序
原理 最简单的一种排序算法。假设长度为n的数组arr要按照从小到大的排序则冒泡排序的具体过程可以描述为首先从数组的第一个元素开始到数组的最后一个元素为止对数组中相邻的两个元素进行比较如果相邻两个元素中左边的元素大于右边的元素则交换两个元素的位置此时数组最右端的元素即为该数组中所有元素的最大值。接着对该数组剩下的n-1个元素进行冒泡排序直到整个数组有序排列。
时间复杂度 O(n^2)。
动态直观图
代码实现
import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int[] arr new int[]{3,78,34,50,89,1,45,7};System.out.println(排序之前 Arrays.toString(arr));bubbleSort(arr);System.out.println(排序之后 Arrays.toString(arr));}/*** 冒泡排序* param arr*/public static void bubbleSort(int[] arr){for(int i arr.length - 1; i 0; i--){for(int j 0; j i; j){if(arr[j] arr[j 1]){int tem arr[j];arr[j] arr[j 1];arr[j 1] tem;}}}}
}结果
排序之前[3, 78, 34, 50, 89, 1, 45, 7]
排序之后[1, 3, 7, 34, 45, 50, 78, 89]1.2、简单选择排序
原理 在严蔚敏版本的《数据结构》中对选择排序的基本描述为每一轮在n-i1(i1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第 i个记录。假设长度为n的数组arr要按照从小到大排序那么先从n个数字中找到最小值min1如果最小值min1的位置不在数组的最左端也就是min1不等于arr[0]则将最小值arr[0] min1接着在剩下的(n-1)个数字中找到最小值min2如果最小值min2不等于arr[1]那么则arr[1] min2依次类推直到数组arr有序排列。
时间复杂度 O(n^2)。
直观图解 代码实现
import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr new int[]{3,78,34,50,89,1,45,7};System.out.println(排序之前 Arrays.toString(arr));selectSort(arr);System.out.println(排序之后 Arrays.toString(arr));}/*** 简单选择排序* param arr*/static void selectSort(int[] arr){for(int i0;iarr.length; i){int index i;for(int ji1;jarr.length;j){if(arr[index] arr[j]){index j;}}if(index i){continue;} else {int tem arr[index];arr[index] arr[i];arr[i] tem;}}}}结果
排序之前[3, 78, 34, 50, 89, 1, 45, 7]
排序之后[1, 3, 7, 34, 45, 50, 78, 89]1.3、直接插入排序
原理 插入排序的基本思想就是将无序序列插入到有序序列中。例如将数组arr[4,2,8,0,5,1]排序可以将4看做是一个有序序列图中用蓝色标出将[2,8,0,5,1]看做是一个无序序列无序序列中2比4小于是将2插入到4的左边于是将2插入到4的左边此时有序序列变成了[2,4]无序序列变成了[8,0,5,1]。无序序列中8比4大所以将8插入到4的右边有序序列变成了[2,4,8]无序序列变成了[0,5,1]。依次类推最终数组按照从小到大的排序。
时间复杂度 O(n^2)。
直观图 代码实现
import java.util.Arrays;public class InsertSort {public static void main(String[] args) {int[] arr new int[]{4,2,8,0,5,1};System.out.println(排序之前 Arrays.toString(arr));insertSort(arr);System.out.println(排序之后 Arrays.toString(arr));}static void insertSort(int[] arr){for(int i1;iarr.length;i){//如果数组长度小于1直接返回if(arr.length2)return;//就是j之前的元素都看做是一个有序序列for(int ji;j0;j--){if(arr[j] arr[j-1]){int tem arr[j];arr[j] arr[j-1];arr[j-1] tem;}}}}
}结果
排序之前[4, 2, 8, 0, 5, 1]
排序之后[0, 1, 2, 4, 5, 8]1.4、希尔排序
待续……
1.5、归并排序
待续……
1.6、快速排序
原理 快速怕排序的基本思想是通过一次排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。
实际上 快速排序 冒泡 分治 递归。
一趟快速排序的具体过程可描述为 从待排序列中任意取出一个记录通常选取第一个记录作为基准值然后将记录中比它小的记录都安置在它的位置之前将记录中关键字比它大的记录都安置在它的位置之后。这样以该基准值为分界线将待排序序列分成两个子序列。
一趟快速排序的具体做法为 设置两个指针low和high分别指向待排序列的开始和结尾记录下基准值baseval待排序列的第一个记录然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换重复这两个步骤直到lowhigh为止。
时间复杂度 O(nlogn)。
直观图 代码实现
import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr new int[]{4,2,8,0,5,1};System.out.println(排序之前 Arrays.toString(arr));quickSort(arr,0,arr.length-1);System.out.println(排序之后 Arrays.toString(arr));}/*** 快速排序* param arr 数组* param left 起始位置0* param right 末尾位置 (arr.length-1)*/static void quickSort(int arr[],int left,int right){//左右两指针相与直接返回if(left right){return;}//为了方便起见我们将i和j分别代表左右指针int i left;int j right;//获取基准数(一般是以第一个数为基准数)int baseval arr[left];while (ij){//从右向左找比基准数小的记录,while (ij arr[j] baseval){//如果不小于j指针就继续左移j--;}//从左向右找比基准数大的记录,while (ij arr[i] baseval){//如果不大于i指针就继续右移i;}//当j指针找打了比基准数小的值当i指针找到比基准值大的值交换两者的位置int tem arr[i];arr[i] arr[j];arr[j] tem;}//当两指针相遇时也就是ij了将此位置的值与基准值baseval交换arr[left] arr[i];arr[i] baseval;//递归排序左右两边的序列quickSort(arr,left,i-1);quickSort(arr,i1,right);}
}执行结果
排序之前[4, 2, 8, 0, 5, 1]
排序之后[0, 1, 2, 4, 5, 8]1.7、堆排序
待续……
