标题: Java排序经典解析 [打印本页] 作者: .....淡定 时间: 2013-8-23 16:13 标题: Java排序经典解析 冒泡排序 Bubble Sort
void doBubbleSort(int[] src) {
int len = src.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int temp;
if (src[i] > src[j]) {
temp = src[j];
src[j] = src[i];
src[i] = temp;
}
}
printResult(i, src);
}
}
选择排序 Selection Sort
选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
选择排序与冒泡排序的区别在：冒泡排序每次比较后，如果发现顺序不对立即进行交换，而选择排序不立即进行交换，而是找出最小的元素后再进行交换。
void doChooseSort(int[] src) {
int len = src.length;
int temp;
for (int i = 0; i < len; i++) {
temp = src[i];
int j;
int samllestLocation = i;// 最小数的下标
for (j = i + 1; j < len; j++) {
if (src[j] < temp) {
temp = src[j];// 取出最小值
samllestLocation = j;// 取出最小值所在下标
}
}
src[samllestLocation] = src[i];
src[i] = temp;
printResult(i, src);
}
}
插入排序 Insertion Sort
简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
void doInsertSort2(int[] src) {
int len = src.length;
for (int i = 1; i < len; i++) {
int j;
int temp = src[i];
for (j = i; j > 0; j--) {
if (src[j - 1] > temp) {
src[j] = src[j - 1];
} else
// 如果当前的数，不小前面的数，那就说明不小于前面所有的数，
// 因为前面已经是排好了序的，所以直接通出当前一轮的比较
break;
}
src[j] = temp;
printResult(i, src);
}
}
快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public class QuickSort {
public static int[] QuickSort0(int[] pData, int left, int right) {
int i = left, j = right;
int middle, strTemp;
middle = pData[(left + right) / 2];
do {
while ((pData[i] < middle) && (i < right))
i++;
while ((pData[j] > middle) && (j > left))
j--;
if (i <= j) {
strTemp = pData[i];
pData[i] = pData[j];
pData[j] = strTemp;
i++;
j--;
}
} while (i <= j);
for (int t = 0; t < pData.length; t++)
System.out.print(pData[t] + " ");
System.out.println("");
if (left < j) {
QuickSort0(pData, left, j);
}
if (right > i)
QuickSort0(pData, i, right);
return pData;
}