首页 > 代码库 > 数据结构排序问题---选择---希尔---归并
数据结构排序问题---选择---希尔---归并
选择排序基本思路：设个基准，然后通过循环对比找出最小的
时间复杂度：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]; } } }
数据结构排序问题---选择---希尔---归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。