已知数组int[] max={6,5,2,9,7,4,0};用快速排序算法按降序对其进行排列，并返回数组
public class TestQuickSort {
private int[] array = null;
private void quickSort(int lowest, int highest) {
if (array == null || lowest < 0 || lowest >= highest
|| highest >= array.length) {
return;
}
int low = lowest;
int high = highest;
int key = low++;
for (; low <= high;) {
if (key < high) {
if (array[key] > array[high]) {
array[high] = array[key] + (array[key] = array[high]) * 0;
key = high;
}
high--;
}
if (key > low) {
if (array[key] < array[low]) {
array[low] = array[key] + (array[key] = array[low]) * 0;
key = low;
}
low++;
}
}
quickSort(lowest, key - 1);
quickSort(key + 1, highest);
}
/**
* @param args
*/
public static void main(String[] args) {
TestQuickSort test = new TestQuickSort();
int[] array = {6,5,2,9,7,4,0};
6 5 2 9 7 4 0
0 5 2 9 7 4 6
0 5 2 6 7 4 9
0 5 2 4 7 6 9
0 5 2 4 6 7 9
test.array = array;
test.quickSort(0, array.length - 1);
int length = test.array.length;
for (int i = 0; i < length; i++) {
System.out.println(test.array[i]);
}
}
}
快速排序是综合性能最好的内部排序算法！
一 冒泡排序
[算法描述]
给出N个数，
用第1个与第2个比较，如果N[1]>N[2],则让N[1]与N[2]交换；
用第2个与第3个比较，如果N[2]>N[3],则让N[2]与N[3]交换；
………………
用第N-1个与第N个比较，如果N[N-1]>N[N],则让N[N-1]与N[N]交换；
这样比较一圈后，最大的数就到最后，接着对剩下的N-1个数进行上述的处理，
把这N-1个数中最大的数放到第N-1的位置上,
到最后就排序OK了.由于过程象气泡冒出来，就叫冒泡算法。
[源程序1]顺序冒泡
protected static void MaoPaoSort1(int[] arr){
for(int i=1;i<arr.Length;i++){ //从1到N循环
for(int j=0;j<arr.Length-i;j++){ //从0到N-i循环
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}//end MaoPaoSort1 func
[源程序2]逆序冒泡，先比较第N-1个与第N个
protected static void MaoPaoSort2(int[] arr){
for(int i=0;i<arr.Length-1;i++){
for(int j=arr.Length-1;j>i;j--){
if(arr[j-1] > arr[j]){
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
}//end MaoPaoSort2 func
注：上述程序在循环中如果加入一个标志，如果本次循环中没有发生交换，就退出函数，可以提高一些效率
二 选择排序
[算法描述]
扫描所有数据,选择最小的数据与第1个数据互换;
扫描除第1个以外的所有数据,选择最小的数据与第2个数据互换;
………………
扫描除第N-2个以外的所有数据,选择最小的数据与第N-1个数据互换;
排序完成，进行N-1次扫描
[源程序]
protected static void SelectSort(int[] arr){
for(int i=0;i<arr.Length-1;i++){
int smallNo = i;
for(int j=i+1;j<arr.Length;j++){
if(arr[j] < arr[smallNo]){
smallNo = j; //选出最小数的序号
}
}
if(smallNo != i){ //最小数的序号发生了变化就交换
int tmp = arr[i];
arr[i] = arr[smallNo];
arr[smallNo] = tmp;
}
}
}//end SelectSort func
三 插入排序
[算法描述]
首先把数组第一个元素看到排序好的数组，
把第二个元素插入到排序好的数组中，
再把第三个元素插入到前两个排序好的数组中，如此类推
往一个有序数组中插入一个元素X，使数组依然有序
1.从左至右扫描数组,从第1个大于元素X的数组元素K开始,
其后的元素依次右移一位，并把X存储于K的位置；
2.如果大于元素X的数组元素不存在，则在数组末尾插入X
[源程序]
protected static void InsertSort(int[] arr){
int ins,i=0,j=0;
for(i=1;i<arr.Length;i++){
ins = arr[i]; //等待插入的元素
if(ins < arr[i-1]){ //i之前（不包括i）的元素是已经排序好的
j = i-1;
while( j>=0 && ins < arr[j]){//这里需要注意一下：不能写成 ins < arr[j] &&j>=0
arr[j+1] = arr[j]; //把大于ins的元素依次后移
j--; //后移直到让出ins的位置为止
}
arr[j+1] = ins;
}
}//end for i
}//end InsertSort func
四 快速排序
[算法描述]
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.以数组的中间元素为参考值;
2.将中间元素左边大于参考值的与中间元素右边小于参考值的元素互换位置;
3.把中间元素左边的所有元素看成数组，递归执行1~4的操作;
4.对中间元素右边的所有元素看成数组，递归执行1~4的操作;
[源程序]
protected static void QuickSort(int[] arr,int leftNo, int rightNo){
int mid = (int)Math.Floor((leftNo + rightNo) / 2);//取得中间点
//Math.Floor(3.6)=3;Math.Ceiling(3.1)=4，用这两种方法都可以
int i = leftNo;
int j = rightNo;
do{
while(arr[i] < arr[mid])i++;
while(arr[j] > arr[mid])j--;
if(i <= j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}while(i<=j);
if(leftNo < j) QuickSort(arr,leftNo,j);
if(rightNo > i)QuickSort(arr,i,rightNo);
}//end QuickSort func