数据结构排序问题---选择---希尔---归并
选择排序基本思路:设个基准,然后通过循环对比找出最小的
时间复杂度:O(n2)
/** * */ package com; /** * @author wenb * @time 下午01:41:21 * @date 2014-10-24 */ public class SelectSort { public static void main(String[] args){ int[] a = {1,3,2,21,5,12,98,54}; Select(a); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } /** * @param a */ private static void Select(int[] a) { // TODO Auto-generated method stub int temp; for(int i=0;i<a.length;i++){ //控制整体趟数 int k = i; //找最小的 for(int j =a.length-1;j>i;j--){ if(a[j]<a[k]){ k = j; } } temp = a[i]; a[i] = a[k]; a[k] = temp; } } }
希尔排序基本思路:将整个无序列分割成若干小的子序列分别进行插入排序
时间复杂度:O(n2)
/** * */ package com; /** * @author wenb * @time 下午02:44:18 * @date 2014-10-24 */ public class ShellSort { public static void main(String[] args) { int[] a = {1,3,2,21,5,12,98,54}; shellSort(a); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } public static void shellSort(int[] data) { // 计算出最大的h值 int h = 1; while (h <= data.length / 3) { h = h * 3 + 1; } while (h > 0) { for (int i = h; i < data.length; i += h) { if (data[i] < data[i - h]) { int tmp = data[i]; int j = i - h; while (j >= 0 && data[j] > tmp) { data[j + h] = data[j]; j -= h; } data[j + h] = tmp; } } h = (h - 1) / 3; // 计算出下一个h值 } } }
归并排序基本思路:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
时间复杂度:O(nlogn)
/** * */ package com; import java.util.Arrays; /** * @author wenb * @time 下午03:41:12 * @date 2014-10-24 */ public class MergeSort { public static void main(String[] args) { int[] a = {1,3,2,21,5,12,98,54}; MergeSort.sort(a, 0, a.length-1); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } public static int[] sort(int[] nums, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 左边 sort(nums, low, mid); // 右边 sort(nums, mid + 1, high); // 左右归并 merge(nums, low, mid, high); } return nums; } public static void merge(int[] nums, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; // 把较小的数先移到新数组中 while (i <= mid && j <= high) { if (nums[i] < nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } // 把左边剩余的数移入数组 while (i <= mid) { temp[k++] = nums[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = nums[j++]; } // 把新数组中的数覆盖nums数组 for (int k2 = 0; k2 < temp.length; k2++) { nums[k2 + low] = temp[k2]; } } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。