马鞍山的网站建设公司,干电商需要学什么,在线做投资网站,中核集团八大子公司1 排序算法 1.1 快速排序
1.1.1 算法思想 先取一个随机数#xff0c;然后和数组的最后一个数交换 进行partition过程#xff0c;也就是比数组最后一个数小的放在数组左边#xff0c;大的放在右边#xff0c;相等的在数组中间#xff0c;最后把数组的最后一个数也要放到中…1 排序算法 1.1 快速排序
1.1.1 算法思想 先取一个随机数然后和数组的最后一个数交换 进行partition过程也就是比数组最后一个数小的放在数组左边大的放在右边相等的在数组中间最后把数组的最后一个数也要放到中间位置然后返回相等的那一批数的最左索引和最右索引。 递归前两个过程
1.1.2 时间复杂度
O (N * logN)1.1.3 代码实现
public class QuickSort {private static void quickSort(int[] arr) {if (arr null || arr.length 2) {return;}process(arr, 0, arr.length - 1);}private static void process(int[] arr, int left, int right) {if (left right) {return;}swap(arr, left (int)(Math.random() * (right - left 1)), right);int[] partition partition(arr, left, right);process(arr, left, partition[0] - 1);process(arr, partition[1] 1, right);}private static int[] partition(int[] arr, int left, int right) {int index left;int small left - 1;int big right;while (index big) {if (arr[index] arr[right]) {index;} else if (arr[index] arr[right]) {swap(arr, index, small);}else {swap(arr, index, --big);}}swap(arr, right, big);return new int[] {small, big};}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] arr {1,2,8,9,5};quickSort(arr);for (int i : arr) {System.out.print(i );}}
}1.2 堆排序
1.2.1 算法思想
给了一个数组把数组看成完全二叉树结构现在开始变成堆从完全二叉树的最后一个值开始进行heapify过程也就是把每一个值都要和子节点比较大小把这个节点为顶的树变成堆结构变成大根堆堆结构之后将堆顶元素和数组最后一个元素互换堆的长度减一的同时要进行heapify操作把剩下元素的要恢复堆结构重复第三步操作每次都取一个最大值出来放到原堆的最后数组有序
1.2.2 时间复杂度
O (N * logN)1.2.3 代码实现
public class HeapSort {public static void heapSort(int[] arr) {if (arr null || arr.length 2) {return;}int heapSize arr.length;for (int i arr.length - 1; i 0; i--) {heapify(arr, i, heapSize);}swap(arr, 0, --heapSize);while (heapSize 0) {heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}}private static void heapify(int[] arr, int index, int heapSize) {int left index * 2 1;while (left heapSize) {int largest left 1 heapSize ? (arr[left] arr[left 1] ? left 1 : left) : left;largest arr[index] arr[largest] ? largest : index;if (largest index) {return;}swap(arr, largest, index);index largest;left index * 2 1;}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] arr {1,9,7,3,6,4,8,2,5};heapSort(arr);for (int i : arr) {System.out.print(i );}}
}1.3 桶排序
不基于比较的排序算法分为两类但是都有约束条件
计数排序要排序的数都要是0或正整数基数排序必须是十进制的数而且是0或正整数
给的数越多代价越大。一旦要升级的话要付出的代价更加显而易见。
要排序的最大的数越大计数排序需要的空间就越多要排序比如{9196656412}那么此时就需要辅助数组的长度就要是96656413了很明显性价比不高就需要用基数排序基数排序只用两个辅助数组而且一个计数器数组长度长度固定为10一个辅助数组长度和要排序的数组长度相同浪费的空间小。但是如果要排序的数中最大数越小那么此时就可以用计数排序。
1.3.1 计数排序
算法思想
给定数组范围[0intMax]定义一个辅助数组辅助数组的长度就是给定数组的长度遍历数组给定数组的值与辅助数组的索引对应每当有一个给定数组的值等于辅助数组的索引那么这个索引上的值加一遍历完成之后再遍历辅助数组每当辅助数组的值不为0就把辅助数组的索引覆盖在给定数组中每覆盖一次辅助数组的值减一直到减为0才能遍历下一次
时间复杂度
O (N)代码实现
public class CountSort {public static void countSort(int[] arr) {if (arr null || arr.length 2) {return;}int max arr[0];for (int i 1; i arr.length; i) {max Math.max(max, arr[i]);}int[] bucket new int[max 1];for (int a : arr) {bucket[a];}int index 0;for (int i 0; i bucket.length; i) {while (bucket[i]-- 0) {arr[index] i;}}}// 写比较器验证public static void comparator(int[] arr) {if (arr null || arr.length 2) {return;}Arrays.sort(arr);}public static int[] generateRandomArr(int arrLen) {int[] ans new int[arrLen];for (int i 0; i arrLen; i) {int num (int) (Math.random() * 1000 1);ans[i] num;}return ans;}public static void main(String[] args) {int arrLength 1000;int testTimes 1000000;for (int i 0; i testTimes; i) {int arrLen (int) (Math.random() * arrLength 1);int[] arr1 generateRandomArr(arrLen);int[] arr2 new int[arr1.length];for (int j 0; j arr1.length; j) {arr2[j] arr1[j];}countSort(arr1);comparator(arr2);for (int j 0; j arr1.length; j) {if (arr1[j] ! arr2[j]) {System.out.println(Oops!);}}}System.out.println(Finish!);}
}1.3.2 基数排序
算法思想
算法步骤 给定数组的最大数有几位就遍历几遍最外层的遍历先从个位数字开始遍历 目的是从个位数字开始先把数组中的每个数的个位数字排序之后再排十位以此类推。 第一次遍历 遍历每个数组遍历的过程中只看现在遍历的数的个位数字也就是不管数组有多大每次看的数字只有[0,9] 定义一个计数器数组每个数字出现一个计数器数组的与这个数字相等的索引上的值加一 第二次遍历 遍历计数器数组数组中的每个数等于前面自己的值和前一个数的值相加目的是找出比这个数小的数字有多少个 第三次遍历 定义一个辅助数组长度和给定数组的长度相同从给定数组的末尾开始往前遍历看计数器数字中和给定数组的末尾数字的个为数字相同的数字有几个也就是找比这个数字小的或者等于有多少个这个数字减一就是辅助数组的索引索引上放的数字就是给定数组的现在遍历到的数。这个理解就相当于队列小的肯定在前面相同的先进的先出第一次遍历中先遍历的在前面后遍历的在后面那么最后一个遍历的肯定在最后面 第四次遍历 交换辅助数组和给定数组的每一个值接下来就要结束整个大的个位数的遍历开始遍历十位上的数
时间复杂度
O(N)代码实现
public class RadixSort {public static void radixSort(int[] arr) {if (arr null || arr.length 2) {return;}radixSort(arr, 0, arr.length - 1, maxBits(arr));}// 求数组中最大的数有几位1000 --- 4位private static int maxBits(int[] arr) {int max arr[0];for (int i 1; i arr.length; i) {max Math.max(max, arr[i]);}int ans 0;while (max ! 0) {max / 10;ans;}return ans;}// 基数排序的实现public static void radixSort(int[] arr, int left, int right, int digit) {final int radix 10;int[] help new int[right - left 1];for (int d 1; d digit; d) {int[] count new int[radix];int i 0;int j 0;for (i left; i right; i) {j getDigit(arr[i], d);count[j];}for (i 1; i radix; i) {count[i] count[i - 1];}for (i right; i left; i--) {j getDigit(arr[i], d);help[count[j] - 1] arr[i];count[j]--;}for (i left, j 0; i right; i, j) {arr[i] help[j];}}}// num这个数的digit位的数字(1231) --- 3private static int getDigit(int num, int digit) {return ((num / (int) Math.pow(10, digit - 1)) % 10);}// 对数器测试public static void comparator(int[] arr) {if (arr null || arr.length 2) {return;}Arrays.sort(arr);}public static int generateRandomNum(int num) {return (int) (Math.random() * num 1);}public static int[] generateRandomArr(int arrLen, int num) {int length (int) (Math.random() * arrLen 1);int[] ans new int[length];for (int i 0; i length; i) {ans[i] generateRandomNum(num);}return ans;}public static void main(String[] args) {int num 1000;int arrLen 100;int testTimes 1000000;for (int i 0; i testTimes; i) {int[] arr1 generateRandomArr(arrLen, num);int[] arr2 new int[arr1.length];for (int j 0; j arr1.length; j) {arr2[j] arr1[j];}radixSort(arr1);comparator(arr2);for (int j 0; j arr1.length; j) {if (arr2[j] ! arr1[j]) {System.out.println(Oops!);}}}System.out.println(Finish!);}
}
排序算法总结
1 总结
不基于比较的排序桶排序对样本数据有严格的要求不易改写基于比较的排序只要规定好两个样本怎么比大小就可以直接复用基于比较的排序时间复杂度的极限是O(N*logN)时间复杂度O(N*logN)额外空间复杂度低于O(N)且稳定的基于比较的排序是不存在的为了绝对的速度选择快排为了省空间选堆排为了稳定性选归并
2 常见的坑
归并排序的额外空间复杂度可以变成O(1)“归并排序内部缓存法”但是将变得不稳定。还不如用堆排“原地归并排序”不好会让时间复杂度变成O(N*2)。不如用插入排序快速排序稳定性改进论文“01 stable sort”但是会对样本数据要求更多。不如用桶排序 题目在整型数组中请把奇数放在数组左边偶数放在数组右边要求所有基数之间原始的相对次序不变所有偶数之间原始相对次序不变要求时间复杂度O(N),额外空间复杂度O(1)。
3 排序优化
稳定性的考虑数据是值传递直接快排引用传递用归并排序充分利用O(N*logN)和O(N^2)排序各自的优势小样本量直接插入排序
