?? sort.java
字號:
package org.huhuiyu.datastructures;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* 排序類
*/
public class Sort {
/**
* 快速排序的最小限制
*/
public static final int MIN_LIMIT=10;
/**
* 冒泡(選擇)排序
*
* @param datas
* 要排序的數組
*/
public static void selectionSort(int[] datas) {
boolean check;
for (int i = 0; i < datas.length; i++) {
check = true;
// 交換相鄰的數據，確保最大數被交換到最后的位置
for (int j = 1; j < datas.length - i; j++) {
if (datas[j] < datas[j - 1]) {
Common.swap(datas, j, j - 1);
check = false;
}
}
if (check) { // 如果沒有發生過交換表示數組已經正確排序了
break;
}
}
}
/**
* 插入排序
*
* @param datas
* 要排序的數組
*/
public static void insertionSort(int[] datas) {
insertionSort(datas, 0, datas.length - 1);
}
/**
* 插入排序
*
* @param datas
* 要排序的數組
* @param start
* 起始下標
* @param end
* 結束下標
*/
private static void insertionSort(int[] datas, int start, int end) {
for (int i = start + 1; i <= end; i++) {
int data = datas[i]; // 記下需要插入到合適位置的數據
int j = i - 1;
while (j >= 0 && data < datas[j]) { // 有序的情況就不用循環查找
datas[j + 1] = datas[j]; // 未排序的數據被移動到后面的位置
j--;
}
datas[j + 1] = data; // 將數據插入到空下來的位置
}
}
/**
* 快速排序
*
* @param datas
* 要排序的數組
*/
public static void quickSort(int[] datas) {
quickSort(datas, 0, datas.length - 1);
}
/**
* 快速排序
*
* @param datas
* 要排序的數組
* @param start
* 起始下標
* @param end
* 結束下標
*/
private static void quickSort(int[] datas, int start, int end) {
if (!false) { //正確版本的快速排序
if (end - start <= MIN_LIMIT) {
insertionSort(datas, start, end);
}
else {
int position = partition(datas, start, end);
quickSort(datas, start, position - 1);
quickSort(datas, position + 1, end);
}
}
else { //不穩定的快速排序
if (start < end) {
int position = errorPartition(datas, start, end);
quickSort(datas, start, position - 1);
quickSort(datas, position + 1, end);
}
}
}
/**
* 分區排序
*
* @param datas
* 要排序的數組
* @param start
* 起始下標
* @param end
* 結束下標
* @return 中點下標
*/
private static int errorPartition(int[] datas, int start, int end) {
int basic = datas[start]; // 用區間的第1個記錄作為基準數據
while (start < end) // 從區間兩端交替向中間掃描，直至start=end為止
{
// 虛擬排序過程：
// s e
// 18 32 37 38 22 4 24 21 34 17 0 9
// 17 32 37 38 22 4 24 21 34 17 1 9
// 17 32 37 38 22 4 24 21 34 32 1 8
// 17 4 37 38 22 4 24 21 34 32 1 5
// 17 4 37 38 22 37 24 21 34 32 2 5
// 17 4 18 38 22 37 24 21 34 32 2 2
// 從右向左掃描，查找第1個小于basic的記錄
while (start < end && datas[end] >= basic) {
end--;
}
if (start < end) // 表示找到的第一個小于basic的紀錄
{
datas[start] = datas[end];
start++;
}
// 從左向右掃描，查找第1個關鍵字大于basic的記錄
while (start < end && datas[start] <= basic) {
start++;
}
if (start < end) // 表示找到的第一個大于basic的紀錄
{
datas[end] = datas[start];
end--;
}
}
datas[start] = basic; // 基準記錄已被最后定位
return start; // 將中點位置返回
}
/**
* 分區排序
*
* @param datas
* 要排序的數組
* @param start
* 起始下標
* @param end
* 結束下標
* @return 中點下標
*/
private static int partition(int[] datas, int start, int end) {
// 虛擬排序過程：
// 18 32 37 38 22 4 24 21 34 17
// 17 32 37 38 18 4 24 21 34 22
int mid=(start+end)/2;
sortFirstMiddleLast(datas,start,mid,end);
//放置中點元素到數組結束位置-1，因為最后一個數肯定比它大。
int index=end-1;
Common.swap(datas, mid, end-1);
int middata=datas[index]; //支點的數據
// 17 32 37 38 34 4 24 21 18 22
//需要比較的數組范圍
int left=start+1; //第一個肯定比支點元素小，不用在比較
int right=end-2; //最后兩個是不用比較的
// s e
// 17 32 37 38 34 4 24 21 18 22 1 7
// 17 4 37 38 34 32 24 21 18 22 2 4
// 17 4 18 38 34 32 24 21 37 22 2 2
while(true){
while(datas[left]<middata){ //查找第一個比支點的數據大的數據
left++;
}
while(datas[right]>middata){ //查找第一個比支點的數據小的數據
right--;
}
if(left<right){ //如果找到相應的數據就交換位置
Common.swap(datas, left, right);
left++;
right--;
}
else{ //否則就表示找到了中點
break;
}
}
//放置中點元素到正確的位置
Common.swap(datas, index, left);
index=left;
return index;
}
/**
* 排序3個指定位置的數組元素
*
* @param datas
* 要排序的數組
* @param start
* 起點
* @param mid
* 中點
* @param end
* 終點
*/
private static void sortFirstMiddleLast(int[] datas, int start,int mid, int end){
if(datas[start]>datas[mid]){
Common.swap(datas, start, mid);
}
if(datas[mid]>datas[end]){
Common.swap(datas, mid, end);
}
if(datas[start]>datas[mid]){
Common.swap(datas, start, mid);
}
}
/**
* java自帶排序演示
*/
public static void javaSort() {
SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss,SSS");
int[] datas = Common.getRandomData(200000);
System.out.println(sdf.format(new Date()) + "-排序前：");
Common.showArray(datas, 10);
java.util.Arrays.sort(datas);
System.out.println(sdf.format(new Date()) + "-排序后：");
System.out.printf("是否正確排序：%b%n", Common.checkSort(datas));
Common.showArray(datas, 10);
}
public static void main(String[] args) {
System.out.println("java自帶排序");
javaSort();
System.out.println("+++++++++++++++++++++++++++++++++++");
SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss,SSS");
int[] datas = Common.getRandomData(20);
System.out.println(sdf.format(new Date()) + "-排序前：");
Common.showArray(datas, 10);
Sort.selectionSort(datas);
System.out.println(sdf.format(new Date()) + "-排序后：");
System.out.printf("是否正確排序：%b%n", Common.checkSort(datas));
Common.showArray(datas, 10);
System.out.println("+++++++++++++++++++++++++++++++++++");
datas = Common.getRandomData(200000);
System.out.println(sdf.format(new Date()) + "-排序前：");
System.out.printf("是否正確排序：%b%n", Common.checkSort(datas));
Common.showArray(datas, 10);
Sort.quickSort(datas);
System.out.println(sdf.format(new Date()) + "-排序后：");
System.out.printf("是否正確排序：%b%n", Common.checkSort(datas));
Common.showArray(datas, 10);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -