西安地区专业做网站公司,库尔勒 网站建设,广州网站建设开发团队,wordpress 视频预览本文将围绕冒泡排序、桶排序、计数排序、堆排序、插入排序、并归排序、快速排序和选择排序#xff0c;按照描述、时间复杂度(最坏情况)、动态图展示和代码实现来讲解。本文默认排序为从小到大。本文相关代码已上传至github#xff0c;欢迎关注https://github.com/zhuzhenke/c…本文将围绕冒泡排序、桶排序、计数排序、堆排序、插入排序、并归排序、快速排序和选择排序按照描述、时间复杂度(最坏情况)、动态图展示和代码实现来讲解。本文默认排序为从小到大。本文相关代码已上传至github欢迎关注https://github.com/zhuzhenke/common-algorithms公用方法SortUtilspublic class SortUtils {public static void check(int[] sortingData) {if (sortingData null || sortingData.length 0) {throw new IllegalArgumentException(sortingData can not be empty!);}}public static void swap(int[] swapArray, int i, int j) {check(swapArray);if (i 0 || i swapArray.length - 1) {throw new ArrayIndexOutOfBoundsException(illegal index i: i);}if (j 0 || j swapArray.length - 1) {throw new ArrayIndexOutOfBoundsException(illegal index j: j);}int temp swapArray[i];swapArray[i] swapArray[j];swapArray[j] temp;}public static int getMaxValue(int[] sortingData) {check(sortingData);int max sortingData[0];for (int value : sortingData) {if (value 0) {throw new IllegalArgumentException(value could not be negative: value);}if (value max) {max value;}}return max;}}冒泡排序描述比较前后两个数的大小如果前者大于后者则交换两个数的位置最大的数字在进行一轮比较和交换后会出现在数组的最后一个位置每一轮之后可减少最大数字的比较。重复上述操作直到没有需要比较的元素为止时间复杂度O(n^2)动态图展示代码实现github代码public int[] sort(int[] sortingData) {SortUtils.check(sortingData);for (int j sortingData.length - 1; j 0; j--) {for (int i 0; i j; i) {if (sortingData[i] sortingData[i 1]) {SortUtils.swap(sortingData, i, i 1);}}}return sortingData;}桶排序描述挑选数组中最大的数字设置默认分配的桶数得到每个桶容纳的数字范围。如最大是10桶是4个则每个桶最大容纳3个数字。第0个桶放0、1、2、3第1个桶方4、5、6,第2桶方789以此类推对每个桶内进行冒泡排序或选择排序遍历所有桶依次取出每个桶中的元素得到的就是一个排好序的数组时间复杂度O(n^2)动态图展示代码实现github代码Overridepublic int[] sort(int[] sortingData) {SortUtils.check(sortingData);int bucketSize (int) Math.round(Math.sqrt(sortingData.length)) 1;int[][] buckets new int[bucketSize][];int max SortUtils.getMaxValue(sortingData);double avgContain Math.ceil((double) max / (double) bucketSize);for (int value : sortingData) {int bucketIndex (int) Math.ceil(value / avgContain) - 1;if (bucketIndex 0) {bucketIndex 0;}int[] bucketIndexs buckets[bucketIndex];if (bucketIndexs null || bucketIndexs.length 0) {bucketIndexs new int[1];bucketIndexs[0] value;buckets[bucketIndex] bucketIndexs;} else {int[] newBucketIndexs new int[bucketIndexs.length 1];System.arraycopy(bucketIndexs, 0, newBucketIndexs, 0, bucketIndexs.length);newBucketIndexs[bucketIndexs.length] value;buckets[bucketIndex] newBucketIndexs;}}Sort sort new InsertionSort();for (int a 0; a buckets.length; a) {int[] bucket buckets[a];if (bucket null || bucket.length 0) {continue;}bucket sort.sort(bucket);buckets[a] bucket;}int[] result new int[sortingData.length];int resultIndex 0;for (int[] bucket : buckets) {if (bucket null || bucket.length 0) {continue;}for (int bucketValue : bucket) {result[resultIndex] bucketValue;}}return result;}计数排序描述获取数组中最大的值(这个值需要在可控范围最好是在10000以内)创建一个长度为最大值加1的计数数组遍历待排序数组将元素的值落入到计数数组的下标元素将下标元素的值加1遍历下标数组将后一个元素的值标为当前元素值加前一个元素的值(用于排序后的数组下标)。创建一个长度跟待排序数组大小相同的结果数组遍历待排序数组取出待排序元素对应计数数组的下标元素并放在计数元素值的前一个位置并将计数元素值减1时间复杂度O(n)动态图展示代码实现github代码private int[] sort2(int[] sortingData) {int maxValue SortUtils.getMaxValue(sortingData);//get max,check all numbers must be bigger or equal 0int[] count new int[maxValue 1];//count every numberfor (int value : sortingData) {count[value] count[value] 1;}for (int i 1; i count.length; i) {count[i] count[i] count[i - 1];}//outputint[] result new int[sortingData.length];for (int value : sortingData) {result[count[value] - 1] value;count[value] count[value] - 1;}return result;}堆排序描述为了方便理解将数组元素映射成二叉树array[0]对一个根节点array[1]为根的左节点array[2]为根的右节点一次类推从最后一个元素开始遍历到第一个让其与父节点比较大小如果子节点大则交换位置。(另外一种方式是从中间元素开始比较得到当前元素和子元素的最大值这样则遍历深度为logn,这种方式属于推荐方式)遍历一轮结束后则最大值已经位于index为0的位置这时交换index为0和最后一位的位置则最大值确定。下一轮比较从最大值的前一个index下标元素开始遍历依次进行遍历最后全部遍历完成则得到一个拍好序的数组时间复杂度O(nlogn)动态图展示代码实现github代码public int[] sort(int[] sortingData) {int highIndex sortingData.length - 1;while (highIndex 0) {for (int i 1; i highIndex; i) {sortBiggestToIndex0(sortingData, i);}SortUtils.swap(sortingData, 0, highIndex);highIndex--;}return sortingData;}public static void sortBiggestToIndex0(int[] sortingData, int sortIndex) {while (sortIndex 0 sortingData[sortIndex] sortingData[(sortIndex - 1) / 2]) {SortUtils.swap(sortingData, sortIndex, (sortIndex - 1) / 2);sortIndex (sortIndex - 1) / 2;}}插入排序描述插入排序类似于扑克摸牌排序第一次只有一种牌牌是有序的。当摸到第二张牌时则插入到已有的排好序的牌中此时前两张牌有序依次进行同样的操作摸到第n张牌时前n-1张牌已经有序进行插入到合适位置即可时间复杂度O(n^2)动态图展示代码实现github代码public int[] sort(int[] sortingData) {SortUtils.check(sortingData);for (int i 1; i sortingData.length; i) {int currentValue sortingData[i];int j i;while (j - 1 0 currentValue sortingData[j - 1]) {sortingData[j] sortingData[j - 1];j--;}sortingData[j] currentValue;}return sortingData;}并归排序描述并归排序利用递归思想递归思想的核心在于找到一个模式分解为子模式子模式又可以分解子模式则对于最小子模式可以直接求解。首先会将待排序数组分为两份两份分别排好序后进行合并两份中的每一份又可以查分为更小的一份直到每份只有一个元素则此份为已排好序的子数组。对两个子数组进行合并的排序时间复杂度O(nlogn)动态图展示代码实现github代码Overridepublic int[] sort(int[] sortingData) {SortUtils.check(sortingData);splitDate(sortingData, 0, sortingData.length - 1);return sortingData;}private void splitDate(int[] sortingData, int start, int end) {if (end - start 1) {return;}int middle (start end) / 2;splitDate(sortingData, start, middle);splitDate(sortingData, middle 1, end);mergeData(sortingData, start, middle, end);}private void mergeData(int[] sortingData, int start, int middle, int end) {int[] left Arrays.copyOfRange(sortingData, start, middle 1);int[] right Arrays.copyOfRange(sortingData, middle 1, end 1);int i 0;int j 0;for (int k start; k end; k) {if (i left.length j right.length) {if (left[i] right[j]) {sortingData[k] left[i];i;} else {sortingData[k] right[j];j;}} else {if (i left.length) {sortingData[k] right[j];j;} else if (j right.length) {sortingData[k] left[i];i;}}}}快速排序描述选择待排序数组的中元元素一般选择第一个或最后一个元素将数组拆分为两部分左边部分元素小于等于中元元素右边部分元素大于中元元素继续将子数组按中元元素进行拆分直到全部排好序位置时间复杂度O(n^2)动态图展示代码实现github代码Overridepublic int[] sort(int[] sortingData) {SortUtils.check(sortingData);quickSort(sortingData, 0, sortingData.length - 1);return sortingData;}private void quickSort(int[] sortingData, int start, int end) {if (start end) {return;}int middle getQuickSortMiddle(sortingData, start, end);quickSort(sortingData, start, middle - 1);quickSort(sortingData, middle 1, end);}/*** one side*/public int getQuickSortMiddle(int[] sortingData, int start, int end) {int i start;int pivot end;for (int j start; j end; j) {if (sortingData[j] sortingData[pivot]) {SortUtils.swap(sortingData, i, j);i;}}SortUtils.swap(sortingData, i, pivot);return i;}选择排序描述从第一个元素开始遍历记录最小值和对应元素下标遍历一轮则可以得到最小值将这个值与下标为0的元素交换则完成第一轮最小值输出从第2个进行同样的遍历操作遍历取剩余元素的最小值将这个值与下标为1的元素交换从第index个开始进行遍历操作遍历取剩余元素的最小值将这个值与下标为index的元素交换遍历直到最后一个元素位置得到一个排好序的数组时间复杂度O(n^2)动态图展示代码实现github代码public int[] sort(int[] sortingData) {SortUtils.check(sortingData);for (int index 0; index sortingData.length; index) {int smallestIndex index;int smallestValue sortingData[index];for (int j index; j sortingData.length; j) {if (sortingData[j] smallestValue) {smallestValue sortingData[j];smallestIndex j;}}sortingData[smallestIndex] sortingData[index];sortingData[index] smallestValue;}return sortingData;}
