package cn.by.Struct.Sort;
public class Sort {
/**
* 插入排序
*
* 基本思想：
* 每一趟將一個待排序的記錄，按其關鍵字值的大小插入到已經排序的
* 部分文件中適當位置上，直到全部插入完成。
*/
/**
* 直接插入排序（插入法）
*
* 逐個將紀錄插入到已排好次序的有序表中得到一個新的有序表.
*
*/
public static void chaSort(int[] table) {
int i,j;
int shao;//哨兵位
for(i = 1; i < table.length; i++) {//要從下標為1的元素開始
shao = table[i];//每次把當前元素賦給哨兵位
j = i – 1;//j每次為有序表的最後一個元素，哨兵位要從它開始比起
while(j >= 0 && shao < table[j]) {//控制邊界，大小判斷找到位置
table[j + 1] = table[j];//元素後移，以便空出一個位置插入shao
j–;//下一次循環
}
table[j + 1] = shao;//找到位置，插入shao,為什麼是j+1呢？因為在while退出的
//時候，j的位置是指向小於或等於shao的元素，所以shao的位置j要加1
}
}
/**
* 希爾（shell）排序
*
* 基本思想：
*
* 把記錄按下標的一定增量d分組，對每組記錄采用直接插入排序方法進行排序，隨著增量逐漸減小，所分成的組包
* 含的記錄越來越多，當增量的值減小到1時，整個數據合成為一組，構成一組有序記錄，則完成排序。
*
* @param table
* @param n 元素個數
*/
public static void shellSort(int table[], int n) {
int i;
int j;
int shao;//哨兵位
int gap = n/2;//初始增量為長度減1
while(gap > 0) {
for(i = gap; i < n; i++) {//對所有相隔gap位置的所有元素進行排序
shao = table[i];//每次把當前元素賦給哨兵位
j = i – gap;//j每次為有序表的最後一個元素，哨兵位要從它開始比起
while(j >= 0 && shao < table[j]) {//對相隔gap位置的元素組進行排序
table[j + gap] = table[j];//元素後移，以便空出一個位置插入shao
j = j – gap;//下一次循環
}
table[j + gap] = shao;//找到位置，插入shao,為什麼是j+gap呢？因為在while退出的
//時候，j的位置是指向小於或等於shao的元素，所以shao的位置j要加gap
}
gap = gap/2;//
}
}
/**
* 選擇排序
*
* 基本思想：
* 每步從待排序的記錄中選出關鍵字最小的記錄，按順序放在已排序的記錄序列的最後，
* 直到全部排完為止。
*
*/
/**
* 直接選擇排序
*
* 進行n-1趟，每一趟逐個與剩餘元素比較，找到小的就與之交換。
*/
public static void selectSort(int table[]) {
int temp;//用於交換
for(int i = 0; i < table.length – 1; i++) {
for(int j = i + 1; j < table.length; j++ ){
if(table[i] > table[j]) {
temp = table[i];
table[i] = table[j];
table[j] = temp;
}
}
}
}
/**
*交換排序
*
*基本思想:
*兩兩比較待排序記錄的關鍵字，並交換不滿足次序要求的那些偶對，直到全部滿足為止。
*/
/**
*冒泡排序
*
*相鄰之間相比較.n個元素要進行n-1趟。每趟要比較n減該趟（當前趟）次。
*
*從後向前冒，冒出最小的數
*@param array 要查的一個數組
*@return 無返回值
*/
public static void maoSort(int[] table) {
/**
*主要用於提前結束比較,即如果一趟中沒有一個元素交換， 則後面還沒有進行的趟也不用進行瞭。
*/
int exchange;
// 臨時交換變量
int temp;
for (int i = 1; i <= table.length – 1; i++) {//要走的趟數
exchange = 0; // 初始值為0
for (int j = table.length – 1; j > i – 1; j–)//每趟要交換的次數
if (table[j] < table[j – 1]) {
temp = table[j];
table[j] = table[j – 1];
table[j – 1] = temp;
exchange = 1; // 如有交換則更改為1
}
// 提前結束
if (exchange == 0)
return;
}
}
/**
*快速排序：
*
*通過一趟排序將待排序記錄分割成獨立的兩部分，
*其中一部分記錄的關鍵字均比另一部分的關鍵字小，再分別
*對這兩部分記錄繼續進行排序，以達到整個序列有序。
*
*@param table-待排序數組
*@param begin-待排序的起始源點
*@param end-待排序的終止點
*/
public static void quickSort(int []table, int begin, int end) {
//異常處理，待排序的起始源點不能小於0且不能大於待排序的終止點
if((begin < 0) || (begin > end))
return;
int i = begin;
int j = end;
int tem;
//存放界點,用區間的第一個元素作基準
tem = table[begin];
//從區間兩端交替向中間掃描，直至i=j為止
while(i != j) {
//從右向左掃描，找第一個小於tem的元素
while((j > i) && table[j] > tem)
j–;
//從左向右掃描，找第一個大於tem的元素
while((i < j) && table[i] < tem)
i++;
//滿足條件交換
if(i < j) {
int change;
change = table[j];
table[j] = table[i];
table[i] = change;
}
}
//分成兩部分記錄
table[i] = tem;
//對界點前部分記錄排序
quickSort(table, begin, i – 1);
//對界點後部分記錄排序
quickSort(table, i + 1, end);
}
}
本文出自 “Enthusiasm 10年” 博客
