/**
* 选择选择排序
* 1. 基本思想:
* 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
* 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
* 2. 排序过程:
* 【示例】:
* 初始关键字 [49 38 65 97 76 13 27 49]
* 第一趟排序后 13 [38 65 97 76 49 27 49]
* 第二趟排序后 13 27 [65 97 76 49 38 49]
* 第三趟排序后 13 27 38 [97 76 49 65 49]
* 第四趟排序后 13 27 38 49 [49 97 65 76]
* 第五趟排序后 13 27 38 49 49 [97 97 76]
* 第六趟排序后 13 27 38 49 49 76 [76 97]
* 第七趟排序后 13 27 38 49 49 76 76 [ 97]
* 最后排序结果 13 27 38 49 49 76 76 97
* @param data
* @return
*/
public int[] selectionSort( int[] data ){
for( int i = 0; i < data.length; i++ ){
for( int j = i + 1; j < data.length; j++ ){
if( data[i] > data[j]){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
return data;
}
/**
* 快速排序(Quick Sort)
* 1. 基本思想:
* 在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),
* 用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I+1..H],
* 且左边的无序子区中数据元素均小于等于基准元素,
* 右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,
* 即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,
* 分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。
* 2. 排序过程:
*【示例】:
* 初始关键字 [49 38 65 97 76 13 27 49]
* 第一次交换后 [27 38 65 97 76 13 49 49]
* 第二次交换后 [27 38 49 97 76 13 65 49]
* J向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49]
* I向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49]
* J向左扫描 [27 38 13 49 76 97 65 49]
*(一次划分过程)
* 初始关键字 [49 38 65 97 76 13 27 49]
* 一趟排序之后 [27 38 13] 49 [76 97 65 49]
* 二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
* @param data
* @return
*/
public int[] quickSort( int[] data ){
quickSort( data, 0, data.length - 1);
return data;
}
private void quickSort( int[] data, int low, int high ){
if( low >= high ){
return;
}
int l = low;
int h = high;
boolean direction = true; //true means from right to left; false mean from left to right
while( l < h ){
if( direction ){
if( data[h] < data[l]){
int temp = data[h];
data[h] = data[l];
data[l] = temp;
direction = false;
l++;
}else{
h--;
}
}else{
if( data[h] < data[l]){
int temp = data[h];
data[h] = data[l];
data[l] = temp;
direction = true;
h--;
}else{
l++;
}
}
}
this.quickSort(data, low, l -1 );
this.quickSort(data, h+1, high );
}
public static void main( String[] args ){
int[] data = {49,38,65, 97,76,13,27,49};
Sorter s = new Sorter();
int[] result = s.quickSort(data);
for( int i : result ){
System.out.print( i + " ");
}
}
}