Java实现各种排序汇总
jopen
11年前
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
那什么是稳定的排序算法呢？
就是在排序的过程中，相等的两个数并不会在排列后中为位置发生次序发生颠倒
</div>
再看一下各排列算法的时间效率分析汇总：
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9)， R是基数(个十百) |
| 希尔 | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
一、冒泡排序
/** * 冒泡排序 * * @author 陈雪桂 * */ public class BubbleSort { public static void main(String[] args) { BubbleSort b = new BubbleSort(); int[] a = b.init(args); a = b.bubbleSort(a); System.out.print("排序结果： "); b.print(a); } /** * 初始化数组 * * @param args * @return */ private int[] init(String args[]) { int[] a = new int[args.length]; for (int i = 0; i < args.length; i++) { a[i] = Integer.valueOf(args[i]); } return a; } /** * 排序核心部分 * * @param a * @return */ private int[] bubbleSort(int[] a) { int temp; for (int i = 0; i < a.length; i++) for (int j = 0; j < a.length - i - 1; j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } return a; } /** * 打印 * @param a */ private void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } 二、选择排序
/** * 选择排序 * * @author 陈雪桂 * */ public class SelectionSort { public static void main(String[] args) { SelectionSort s = new SelectionSort(); int[] a = s.init(args); a = s.selectionSort(a); System.out.print("排序结果： "); s.print(a); } /** * 初始化数组 * * @param args * @return */ private int[] init(String args[]) { int[] a = new int[args.length]; for (int i = 0; i < args.length; i++) { a[i] = Integer.valueOf(args[i]); } return a; } /** * 选择排序核心 * * @param a * @return */ private int[] selectionSort(int[] a) { int min; int temp; for (int i = 0; i < a.length; i++) { min = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[min]) { min = j; } } temp = a[i]; a[i] = a[min]; a[min] = temp; } return a; } /** * 打印 * * @param a */ private void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } 三、插入排序
/** * 插入排序 * * @author Administrator * */ public class InsertSort { public static void main(String[] args) { InsertSort insertSort = new InsertSort(); int[] a = insertSort.init(args); a = insertSort.insertSort(a); System.out.print("排列顺序： "); insertSort.print(a); } // 初始划排列数组 private int[] init(String[] args) { int[] j = new int[args.length]; for (int i = 0; i < args.length; i++) { j[i] = Integer.valueOf(args[i]); } return j; } // 增序排列 private int[] insertSort(int[] a) { int temp; for (int i = 1; i < a.length; i++) { temp = a[i]; int j = i - 1; for (; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } return a; } private void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } 四、基数排序
/** * 基数排序 平均时间复杂度：O(dn)(d即表示整形的最高位数) * 空间复杂度：O(10n) （10表示0~9，用于存储临时的序列） * 稳定性：稳定 * * @author 陈雪桂 * */ public class RadixSort { /** * 最大数的位数 */ static int max_Pos = 2; public static void main(String[] args) { RadixSort r = new RadixSort(); int[] a = r.init(args); a = r.radixSort(a, a.length); System.out.print("排列结果: "); r.print(a); } /** * 初始化数组 * * @param args * @return */ private int[] init(String args[]) { int[] a = new int[args.length]; for (int i = 0; i < args.length; i++) { a[i] = Integer.valueOf(args[i]); } return a; } private int[] radixSort(int[] data, int dataSize) { List<Integer>[] bucket = new ArrayList[10]; for (int pos = 1; pos <= max_Pos; pos++) { for (int i = 0; i < dataSize; i++) { int num = getNumAtPos(data[i], pos - 1); if (null == bucket[num]) { bucket[num] = new ArrayList<Integer>(); } bucket[num].add(data[i]); } for (int i = 0, j = 0; i < 10; i++) { for (int k = 0; bucket[i] != null && k < bucket[i].size(); k++) { data[j++] = bucket[i].get(k); } if (bucket[i] != null) { bucket[i].clear(); } } } return data; } /** * 获取当前位上数字 * * @param num * @param pos * @return */ private int getNumAtPos(int num, int pos) { int temp = 1; for (int i = 0; i < pos; i++) { temp *= 10; } return (num / temp) % 10; } private void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } 五、希尔排序
/** * 希尔排序 * * @author 陈雪桂 * */ public class ShellSort { public static void main(String[] args) { ShellSort s = new ShellSort(); int[] a = s.init(args); a = s.shellSort(a); System.out.print("排列顺序 ： "); s.print(a); } /** * 初始化数组 * * @param args * @return */ private int[] init(String args[]) { int[] a = new int[args.length]; for (int i = 0; i < args.length; i++) { a[i] = Integer.valueOf(args[i]); } return a; } /** * 希尔排序核心1 * * @param args * @return */ private int[] shellSort(int[] a) { for (int step = a.length / 2; step >= 1; step = step/2) { a = shellInsert(a, step); } return a; } /** * 增序排列 * * @param a * @param step * @return */ private int[] shellInsert(int[] a, int step) { int min = 0; for (int i = step; i < a.length; i++) { if (a[i] < a[i - step]) { min = a[i]; int j; for (j = i - step; j >= 0 && a[j] > min; j -= step) { a[j + step] = a[j]; } a[j + step] = min; } } return a; } /** * 打印 * * @param a */ private void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } 六、快速排序
/** * 快速排序 * * @author 陈雪桂 * */ public class QuickSort { static int count = 0; public static void main(String[] args) { QuickSort q = new QuickSort(); int[] list = new int[12]; for (int i = 0; i < args.length; i++) { list[i] = Integer.valueOf(args[i]); } q.quickSort(list, 0, list.length - 1); System.out.print("排序顺序： "); for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } System.out.println("\n执行次数：" +count ); } public void quickSort(int[] n, int from, int to) { if (from <= to) { int midSort = partition(n, from, to); quickSort(n, from, midSort - 1); quickSort(n, midSort + 1, to); } return; } public int partition(int[] n, int from, int to) { int i = from + 1; int j = to; int p = n[from]; while (i < j) { while (n[i] < p) i++; while (n[j] > p) j--; swap(n, i, j); count ++; } // 判断是否有必要撤销最后一次交换，必要则不用在循环中加入边界检查条件 if(i != from+1 || j !=to)swap(n, i, j); swap(n,from,j); return j; } public void swap(int[] n, int i, int j) { int temp = n[i]; n[i] = n[j]; n[j] = temp; } } 七、合并排序
/** * 合并排序 * @author 陈雪桂 * */ public class MergeSort { public static void main(String[] args) { int[] list = new int[12]; for (int i = 0; i < args.length; i++) { list[i] = Integer.valueOf(args[i]); } list = new MergeSort().mergeSort(list, 0, list.length-1); System.out.print("排列顺序: "); for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } } public int[] mergeSort(int[] list, int from, int to) { if (from != to) { int mid = (from + to) / 2; mergeSort(list, from, mid); mergeSort(list, mid + 1, to); return merge(list, from, to); } return list; } public int[] merge(int[] list, int from, int to) { int i = from; int mid = (from + to) / 2; int j = mid + 1; int[] a = new int[to - from + 1]; int count = 0; while (i <= mid && j <= to) { if (list[i] < list[j]) { a[count++] = list[i++]; } else { a[count++] = list[j++]; } } // 把剩余部分都加进去 while (i <= mid) { a[count++] = list[i++]; } while (j <= to) { a[count++] = list[j++]; } for(int k=from; k<= to; k++) { list[k] = a[k-from]; } return list; } } 八、堆排序
/** * 堆排序包括两个步骤 (1)初始堆(堆的定义：(1)堆是一个完全二叉树(2)根结点的值或者大于左右子树的值或者小于左右子树的值(3)左右子树也是一个堆) * (2)调整堆(当初始小顶堆之后，堆顶元素是最小的元素，取出最小的元素与最后一个元素相交换，再把剩下n-1个元素调整成堆,依次调整直到1为止) * 非终端节点调整 初始堆时从n/2向上调整成堆 把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆 * * * 时间复杂度为O(nlogn) 辅助空间为O(1) * * @author 陈雪桂 * */ public class HeapSort { public static void main(String[] args) { HeapSort h = new HeapSort(); int[] a = init(args); heapSort(a); System.out.print("排列顺序： "); print(a); } /** * 初始化数组 * * @param args * @return */ private static int[] init(String[] args) { int[] a = new int[args.length]; for (int i = 0; i < args.length; i++) { a[i] = Integer.valueOf(args[i]); } return a; } /** * 堆排序核心部分 * * @param num */ private static void heapSort(int[] num) { int temp; // 初始建堆从n/2开始向根调整 for (int i = num.length / 2 - 1; i >= 0; i--) { adjustHeap(num, i, num.length);// 初始堆过程 } for (int i = num.length - 1; i > 0; i--) { // 将堆顶元素与i元素交换 temp = num[i]; num[i] = num[0]; num[0] = temp; // 从num[1]到num[i-1]调整成新堆 adjustHeap(num, 0, i - 1); } } /** * 调整堆 * * @param num * @param s * 调整开始父节点 * @param t * 调整结尾的界限 */ private static void adjustHeap(int[] num, int s, int t) { int x = num[s]; // 从最下父节点 与子节点比较，一直向上进行调整 for (int j = 2 * s + 1; j <= t; j = 2 * j + 1) { // 找出较大者把较大者给num[i] if (j < t && num[j] < num[j + 1]) { j = j + 1; } if (j < t && x < num[j]) { num[s] = num[j]; s = j; } } num[s] = x; } /** * 打印 * * @param a */ private static void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }