快速排序法主要是運(yùn)用了Arrays中的一個(gè)方法Arrays.sort（）實(shí)現(xiàn)。
冒泡法是運(yùn)用遍歷數(shù)組進(jìn)行比較，通過(guò)不斷的比較將最小值或者最大值一個(gè)一個(gè)的遍歷出來(lái)。
選擇排序法是將數(shù)組的第一個(gè)數(shù)據(jù)作為最大或者最小的值，然后通過(guò)比較循環(huán)，輸出有序的數(shù)組。
插入排序是選擇一個(gè)數(shù)組中的數(shù)據(jù)，通過(guò)不斷的插入比較最后進(jìn)行排序。
package com.firewolf.sort;
public class MySort {
/**
* @param args
*/
public static void main(String[] args) {
int array[] = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
MySort mySort = new MySort();
mySort.insertSort(array);
System.out.print("插入排序結(jié)果 ： ");
mySort.printArray(array);
System.out.println();
mySort.bubbleSort(array);
System.out.print("冒泡排序結(jié)果 ： ");
mySort.printArray(array);
mySort.qsort(array);
System.out.println();
System.out.print("快速排序結(jié)果 ： ");
mySort.printArray(array);
mySort.shellSort(array);
System.out.println();
System.out.print("希爾排序結(jié)果 ： ");
mySort.printArray(array);
mySort.selectSort(array);
System.out.println();
System.out.print("選擇排序結(jié)果 ： ");
mySort.printArray(array);
}
/**
* 直接插入排序
* 基本思想：在要排序的一組數(shù)中，假設(shè)前面(n-1)[n>=2] 個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序
*/
public void insertSort(int[] array){
int temp=0;
for(int i=1;i<array.length;i++){
int j=i-1;
temp=array[i];
for(;j>=0&&temp<array[j];j--){
array[j+1]=array[j]; //將大于temp的值整體后移一個(gè)單位
}
array[j+1]=temp;
}
}
/**
* 冒泡排序
* 基本思想：在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。
*/
public void bubbleSort(int[] array) {
int temp;
for(int i=0;i<array.length;i++){//趟數(shù)
for(int j=0;j<array.length-i-1;j++){//比較次數(shù)
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
/**
* 快速排序
* 基本思想：選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,通過(guò)一趟掃描，將待排序列分成兩部分,一部分比基準(zhǔn)元素小,一部分大于等于基準(zhǔn)元素,此時(shí)基準(zhǔn)元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分。
* @param array
*/
public void qsort(int array[]){
if(array.length>1){
_qsort(array,0,array.length-1);
}
}
/**
* 一趟快速排序
* @param array
*/
private void _qsort(int[] array,int low,int high){
if(low < high){
int middle = getMiddle(array, low, high);
_qsort(array,low,middle-1);
_qsort(array, middle+1, high);
}
}
/**
* 得到中間值
*/
private int getMiddle(int[] array,int low,int high){
int tmp = array[low];
while(low < high){
while(low < high && array[high] >= tmp)
high--;
array[low] = array[high];
while(low<high && array[low]<=tmp)
low++;
array[high] = array[low];
}
array[low] = tmp;
return low;
}
/**
* 簡(jiǎn)單選擇排序
* 基本思想：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。
* @param array
*/
public void selectSort(int[] array){
int position=0;
for(int i=0;i<array.length;i++){
int j=i+1;
position=i;
int temp=array[i];
for(;j<array.length;j++){
if(array[j]<temp){
temp=array[j];
position=j;
}
}
array[position]=array[i];
array[i]=temp;
}
}
/**
* 希爾排序（最小增量排序）
* 基本思想：算法先將要排序的一組數(shù)按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到1時(shí)，進(jìn)行直接插入排序后，排序完成。
* @param array
*/
public void shellSort(int[] array){
double d1=array.length;
int temp=0;
while(true){
d1= Math.ceil(d1/2);
int d=(int) d1;
for(int x=0;x<d;x++){
for(int i=x+d;i<array.length;i+=d){
int j=i-d;
temp=array[i];
for(;j>=0&&temp<array[j];j-=d){
array[j+d]=array[j];
}
array[j+d]=temp;
}
}
if(d==1)
break;
}
}
/**
* 打印數(shù)組中的所有元素
*/
public void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
}
下面是幾種排序方法分開(kāi)使用的示例
利用Arrays帶有的排序方法快速排序
import java.util.Arrays;
public class Test2{
public static void main(String[] args){
int[] a={5,4,2,4,9,1};
Arrays.sort(a); //進(jìn)行排序
for(int i: a){
System.out.print(i);
}
}
}
冒泡排序算法
public static int[] bubbleSort(int[] args){//冒泡排序算法
for(int i=0;i<args.length-1;i++){
for(int j=i+1;j<args.length;j++){
if (args[i]>args[j]){
int temp=args[i];
args[i]=args[j];
args[j]=temp;
}
}
}
return args;
}
選擇排序算法
public static int[] selectSort(int[] args){//選擇排序算法
for (int i=0;i<args.length-1 ;i++ ){
int min=i;
for (int j=i+1;j<args.length ;j++ ){
if (args[min]>args[j]){
min=j;
}
}
if (min!=i){
int temp=args[i];
args[i]=args[min];
args[min]=temp;
}
}
return args;
}
插入排序算法
public static int[] insertSort(int[] args){//插入排序算法
for(int i=1;i<args.length;i++){
for(int j=i;j>0;j--){
if (args[j]<args[j-1]){
int temp=args[j-1];
args[j-1]=args[j];
args[j]=temp;
}else break;
}
}
return args;
}
以上就是java中的四種排序方法。不同的方法效率不一樣，下面是不同的算法的比較和數(shù)據(jù)交換時(shí)的大O表示。
冒泡排序：比較O(N2) 數(shù)據(jù)交換O(N2)
選擇排序：比較O(N2) 數(shù)據(jù)交換O(N)
插入排序：比較O(N2) 復(fù)制數(shù)據(jù)O(N)
在實(shí)際應(yīng)用中，我們要盡量選擇效率高的算法。
