7种排序算法
7种排序算法
package com.org.momo.排序算法;public class Sort { public static void displayData(int[] data) { for (int d : data) { System.out.print(d + " "); } System.out.println(""); } /** * 快速排序:时间复杂度O(nlogn)，最坏时间复杂度O(n2)，平均时间复杂度O(nlogn)，算法不具稳定性 思想: 基于冒泡排序,取第一个作为关键值a,用a与后面开始往前比较,遇到比a小 的则交换,依然乘此关键值为a,再用a与第一个数开始向后比较,遇到比a大的则 交换,最终的关键值将依然是最初的第一个元素的值,用此值将此无序序列分成两 部分,比它小的都在它前面,大的都在后面,然后用递归将前面和后面的分别用快 速排序进行处理,得到最终的有序序列. */ public static void quickSort(int[] src, int begin, int end) { if (begin < end) { int key = src[begin]; int i = begin; int j = end; while (i < j) { while (i < j && src[j] > key) { j--; } if (i < j) { src[i] = src[j]; i++; } while (i < j && src[i] < key) { i++; } if (i < j) { src[j] = src[i]; j--; } } src[i] = key; quickSort(src, begin, i - 1); quickSort(src, i + 1, end); } } /** * 冒泡排序算法：时间复杂度O(n2)，算法具有稳定性，堆排序和快速排序算法不具 有稳定性，即排序后相同元素的顺序会发生变化 思想: n个数,将第一个和第二个进行比较,将大的放在第二个位置,再将第二个和第 三比较,大的放在第三个位置,依次向后比较,比较n-1次,将最大的放在最后(n的位 置),然后再从第一个开始比较,比较n-2次,这次把最大的放到第n-1个位置,然后再 来回比较.遵循第i次遍历就从第一个数开始比较n-i次,将最后的值放在第n-i+1 的位置. */ public static void bubbleSort(int[] src) { if (src.length > 0) { int length = src.length; for (int i = 1; i < length; i++) { for (int j = 0; j < length - i; j++) { if (src[j] > src[j + 1]) { int temp = src[j]; src[j] = src[j + 1]; src[j + 1] = temp; } } } } } /** * 插入排序:适用于少量数据的排序，时间复杂度O(n2)，是稳定的排序算法，原地排序 * 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序， */ public static void insertSort(int[] a) { int length = a.length; for (int i = 1; i < length; i++) { int temp = a[i]; int j = i; for (; j > 0 && a[j - 1] > temp; j--) { a[j] = a[j - 1]; } a[j] = temp; } } /** * 归并排序算法:稳定排序，非原地排序，空间复杂度O(n)，时间复杂度O(nlogn) * 将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。 * 然后再把有序子序列合并为整体有序序列。 */ public static void mergeSort(int a[], int low, int high) { if (low < high) { mergeSort(a, low, (low + high) / 2); mergeSort(a, (low + high) / 2 + 1, high); merge(a, low, (high + low) / 2, high); } } /** * 归并排序辅助方法，合并 */ private static void merge(int[] a, int low, int mid, int high) { int[] b = new int[high - low + 1]; int s = low; int t = mid + 1; int k = 0; while (s <= mid && t <= high) { if (a[s] <= a[t]) b[k++] = a[s++]; else b[k++] = a[t++]; } while (s <= mid) b[k++] = a[s++]; while (t <= high) b[k++] = a[t++]; for (int i = 0; i < b.length; i++) { a[low + i] = b[i]; } } /** * 选择排序:分为简单选择排序、树形选择排序(锦标赛排序)、堆排序 此算法为简单选择排序 * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后， * 直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 */ public static void selectSort(int[] a) { int length = a.length; for (int i = 0; i < length; i++) { int minIndex = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = a[minIndex]; a[minIndex] = a[i]; a[i] = temp; } } } /** * 希尔排序:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。 * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后， * 取第二个增量d2<d1重复上述的分组和排序， * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)， * 即所有记录放在同一组中进行直接插入排序为止。 */ public static void shellSort(int[] a) { int temp; for (int k = a.length / 2; k > 0; k /= 2) { for (int i = k; i < a.length; i++) { for (int j = i; j >= k; j -= k) { if (a[j - k] > a[j]) { temp = a[j - k]; a[j - k] = a[j]; a[j] = temp; } } } } } /** * 堆排序:最坏时间复杂度O(nlog2n)，平均性能接近于最坏性能。由于建初始堆所需的比较次数多，故堆不适合记录较少的比较 堆排序为原地不稳定排序 */ public static void heapSort(int[] array) { for (int i = 1; i < array.length; i++) { makeHeap(array, i); } for (int i = array.length - 1; i > 0; i--) { int temp = array[i]; array[i] = array[0]; array[0] = temp; rebuildHeap(array, i); } } /** * 堆排序辅助方法---创建堆 */ private static void makeHeap(int[] array, int k) { int current = k; while (current > 0 && array[current] > array[(current - 1) - 6 - 2]) { int temp = array[current]; array[current] = array[(current - 1) / 2]; array[(current - 1) / 2] = temp; current = (current - 1) / 2; } } /** * 堆排序辅助方法---堆的根元素已删除，末尾元素已移到根位置，开始重建 */ private static void rebuildHeap(int[] array, int size) { int currentIndex = 0; int right = currentIndex * 2 + 2; int left = currentIndex * 2 + 1; int maxIndex = currentIndex; boolean isHeap = false; while (!isHeap) { if (left < size && array[currentIndex] < array[left]) { maxIndex = left; } if (right < size && array[maxIndex] < array[right]) { maxIndex = right; } if (currentIndex == maxIndex) { isHeap = true; } else { int temp = array[currentIndex]; array[currentIndex] = array[maxIndex]; array[maxIndex] = temp; currentIndex = maxIndex; right = currentIndex * 2 + 2; left = currentIndex * 2 + 1; } } } public static void main(String[] args) { int data[] = { 2,8,-2,10,0,6,4}; //快速排序 Sort.displayData(data) ; Sort.quickSort(data,0,data.length-1) ; Sort.displayData(data) ; /* //2.冒泡排序 Sort.displayData(data); Sort.bubbleSort(data); Sort.displayData(data); */ } }