java 交换排序算法之二

//(将数组的第一个数作为中间值尔后找出数组中所有比这个中间值(通过循环将值小的与值大的分别进行交换)小的数放在左边,比这
//个中间值大的数放在右边依次下去直至顺序完全正确)
public class QuickSortTest {

/**
* "快速排序法"使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。 首先给出一个数组{
* 53,12,98,63,18,72,80,46,32,21}，先找到第一个数--53，把它作为中间值，
* 也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。 {21，12，32，
* 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序
* 即53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
* 快速排序说到底是从各自两端(不含两端)向中间查找及相互碰头后取出low(左边的一方)作为中间数的地标从
* 而分成以中间数为地界的左右两个数组,而这两个数组再依次继续用同样的方式继续下去，一直到顺序完全正确
*/

public static void main(String[] args) {
// TODO Auto-generated method stub
// //{5,17,13,42,46,94,55,70};
int[] array = { 53, 12, 98, 63, 18, 72, 80, 46, 32, 21 };//
QuickSortTest qst = new QuickSortTest();
qst.quicksort(array, 0, 9);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
System.out.print(",");
}
}

/*
* n就是将进行快速排序的数组，left和right是你数组被排序的左界和右界. 如果要排序上面那个数组，那么left和right分别0,9
*/

void quicksort(int n[], int left, int right) {
int dp;
if (left < right) {
/*
* 这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放到它的左边， ，大的放在右边，然后返回53在整理过的数组中的位置
*/
dp = partition(n, left, right);// 4,0,2,7,6,
// {5,17,13,42,46,94,55,70};
quicksort(n, left, dp - 1);// 边界左边的数组(边界点除外)//4,7
// 这两个就是递归调用，分别整理53左边的数组和右边的数
quicksort(n, dp + 1, right);// 边界左边的数组(边界点除外)//4,
}
}

/**
* @param n 被排序的数组
* @param left 开始排序数组的左下标(index)
* @param right 开始排序数组的右下标
* @return 中间数的座下标
*/
int partition(int n[], int left, int right) {
int low, high, pivot, temp;

pivot = n[left];
low = left - 1;
high = right + 1;
// {5,17,13,42,46,94,55,70};; //
while (low + 1 != high) {// 注意指针的偏移情况
if (n[low + 1] <= pivot) {
low++;
} else if (n[high - 1] > pivot) {
high--;
} else {
temp = n[low + 1];
n[++low] = n[high - 1];
n[--high] = temp;
}
// { 46, 12, 21, 32, 18, 53, 80, 72, 63, 98 } // 第一次取出中间数地标的结果{46,12,21,32,18,53,80,72,63,98,low point=5 high
// point=6}
System.out.println("");
}
n[left] = n[low];
n[low] = pivot;
populate(n);
// System.out.print("low point="+low+" high point="+high);
return low;
}

void populate(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i]);
System.out.print(",");
}
}
}