几种排序算法(JAVA)
一、代码
package com.hdwang; import java.util.Arrays; /**
* Created by admin on 2017/1/20.
*/
public class Sort { /**
* 冒泡排序(最小数冒泡)
* @param array 数组
*/
public void bubbleSort(int[] array){
for(int i=0;i< array.length-1;i++){ //比多少次
for(int j= i+1;j<array.length;j++){ //每次循环,将最小数提前
if(array[i]>array[j]){ //小数冒泡
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
} /**
* 选择排序(选择最小值置前,较冒泡排序空间占用多,速度快(少了交换))
* @param array 数组
*/
public void selectSort(int[] array){
for(int i=0;i<array.length-1;i++){
int minIndex = i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[minIndex]){
minIndex = j; //最小值位置
}
}
//交换最小值与第i位的值
if(minIndex != i){
int tmp = array[minIndex]; //最小值
array[minIndex] = array[i];
array[i] = tmp;
}
}
} /**
* 插入排序(大数后移,小数插入前面,理论上比选择排序空间大,速度快)
* @param array 数组
*/
public void insertSort(int[] array){
for(int i=1;i< array.length;i++){
int tmp = array[i]; //暂存i位的元素,空出来
int j = i;
for(;j > 0 && tmp < array[j-1]; j--){ //前面的大数移到后面来
array[j] = array[j-1];
}
array[j] = tmp; //tmp插入准确位置
}
} /**
* 快速排序(理论上比插入排序空间占用大,排序速度更快)
* @param array 数组
* @param lowIndex 低位索引
* @param highIndex 高位索引
*/
public void quickSort(int[] array,int lowIndex,int highIndex){
if(lowIndex >= highIndex){
return; //退出递归
}
int base = array[lowIndex]; //基准数(小的放其左边,大的放其右边)
int low = lowIndex; //副本
int high = highIndex; //副本
while(low<high){
while(low<high){ //从后面往前找到一个比base小的数,放到前面去(low的位置上去)
if(array[high] < base){
array[low] = array[high];
low++;
break;
}
high--;
}
while(low<high){ // 从前面往后找到一个大于或等于base的数,放到后面去(high的位置上去)
if(array[low] >= base){
array[high] = array[low];
high--;
break;
}
low++;
}
}
array[low] = base; //low==high 结束 quickSort(array,lowIndex,low-1); //递归排序前一段
quickSort(array,low+1,highIndex); //递归排序后一段
} public static void main(String[] args) {
int[] array = {2,3,1,6,9,5,4,2};
System.out.println(Arrays.toString(array)); Sort sort = new Sort();
// sort.bubbleSort(array);
// sort.selectSort(array);
// sort.insertSort(array);
sort.quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array)); }
}
二、输出结果
[2, 3, 1, 6, 9, 5, 4, 2]
[1, 2, 2, 3, 4, 5, 6, 9]