常用的排序方法
package com.util;
/**
?* 常用的排序方法 排序算法的分类如下： 1.插入排序法(直接插入排序法、折半插入排序法、希尔排序法) 2.交换排序法(冒泡排序法、快速排序法)
?* 3.选择排序法(直接选择排序法、堆排序法) 4.归并排序法 5.基数排序法 关于排序方法的选择：
?* (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
?* 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
?* (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
?* (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
?*
?* @author LW
?*/
public class Sort {
?public static final int ASC = 0;// 正序
?public static final int DESC = 1;// 倒序
?/**
? * 交换数据中指定两元素的位置
? *
? * @param data
? * @param x
? * @param y
? */
?private static void swap(int[] data, int x, int y) {
??int temp = data[x];
??data[x] = data[y];
??data[y] = temp;
?}
?/**
? * 插入排序的基本思想为：首先寻找一个有序数列，然后将数组中的每个元素插入到该有序序列中，
? * 则该数组序列即可变为有序数列。具体实施办法为，首选将第一个元素看作是一个有序序列，然后
? * 从第二个元素开始遍历数组，将每个元素插入到从第一个元素到前一个元素的有序序列中，即可完 成排序。
? *
? * @param temp
? */
?public static void insertSort(int[] data) {
??for (int i = 1; i < data.length; i++) {
???int temp = data[i];
???int j = i - 1;
???while (j >= 0 && temp < data[j]) {
????data[j + 1] = data[j];
????j--;
???}
???data[j + 1] = temp;
??}
?}
?/**
? * 折半插入排序算法的java实现
? *
? * @param temp
? */
?public static void bInsertSort(int[] data) {
??int length = data.length;
??for (int i = 1; i < length; i++) {
???int temp = data[i];
???int low = 0;
???int high = i - 1;
???while (low <= high) {
????int middle = (low + high) / 2;
????if (temp < data[middle])
?????high = middle - 1;
????else
?????low = middle + 1;
???}
???for (int j = i; j > high + 1; j--) {
????data[j] = data[j - 1];
???}
???data[high + 1] = temp;
??}
?}
?/**
? *
? * 冒泡排序----交换排序的一种
? *
? * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
? * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
? *
? * @param data
? *??????????? 要排序的数组
? * @param sortType
? *??????????? 排序类型 ASC、DESC
? * @return
? *
? */
?public static void bubbleSort(int[] data, int sortType) {
??if (sortType == ASC) {
???for (int i = 1; i < data.length; i++) {
????for (int j = 0; j < data.length - i; j++) {
?????if (data[j] > data[j + 1]) {
??????swap(data, j, j + 1);
?????}
????}
???}
??} else if (sortType == DESC) {
???for (int i = 1; i < data.length; i++) {
????for (int j = 0; j < data.length - i; j++) {
?????if (data[j] < data[j + 1]) {
??????swap(data, j, j + 1);
?????}
????}
???}
??}
?}
?/**
? *
? * 直接选择排序法----选择排序的一种
? *
? * 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
? * 性能：比较次数O(n^2),n^2/2 交换次数O(n),n
? * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
? * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
? *
? * @param data
? *??????????? 要排序的数组
? * @param sortType
? *??????????? 排序类型
? * @return
? *
? */
?public static void selectSort(int[] data, int sortType) {
??if (sortType == ASC) {
???int index;
???for (int i = 1; i < data.length; i++) {
????index = 0;
????for (int j = 1; j <= data.length - i; j++) {
?????if (data[j] > data[index]) {
??????index = j;
?????}
????}
????swap(data, data.length - i, index);
???}
??} else if (sortType == DESC) {
???int index;
???for (int i = 1; i < data.length; i++) {
????index = 0;
????for (int j = 1; j <= data.length - i; j++) {
?????if (data[j] < data[index]) {
??????index = j;
?????}
????}
????swap(data, data.length - i, index);
???}
??}
?}
}
