常用的排序算法

排序有如下的几种算法: 选择排序，插入排序，希尔排序，冒泡排序，归并排序，快速排序，堆排序，桶排序与基数排序。

选择排序

一般的选择排序

public class SelectSort {    public static void main(String[] args) {	int[] arrays = { 5, 6, 9, 1, 4, 7, 8, 2, 3, 0 };	selectSort(arrays);	for (int i = 0; i < arrays.length; i++) {		System.out.println(arrays[i]);	}}public static void selectSort(int[] arrays) {	for (int i = 0; i < arrays.length - 1; i++) {		for (int j = i + 1; j < arrays.length; j++) {			if (arrays[i] > arrays[j]) {				int temp = arrays[i];				arrays[i] = arrays[j];				arrays[j] = temp;			}		}	}} }

指针选择排序

public class SelectSort {public static void main(String[] args) {	int[] arrays = { 5, 6, 9, 1, 4, 7, 8, 2, 3, 0 };	selectSort(arrays);	for (int i = 0; i < arrays.length; i++) {		System.out.println(arrays[i]);	}	}public static void selectSort(int[] arrays) {	for (int i = 0; i < arrays.length - 1; i++) {		 		int temp = arrays[i];		int index = i ;		for (int j = i + 1; j < arrays.length; j++) {			if (arrays[i] > arrays[j]) {			        i = j ;			}		}				if(i != index) {			arrays[index] = arrays[i];			arrays[i] = temp;		}				i = index;	}}}

插入排序

public class InsertSort {public static void main(String[] args) {	int[] arrays = { 5, 6, 9, 1, 4, 7, 8, 2, 3, 0 };	insertSort(arrays);	for (int i = 0; i < arrays.length; i++) {		System.out.println(arrays[i]);	}}public static void insertSort(int[] arrays) {		for(int i = 1 ; i < arrays.length;i++) {				int temp =arrays[i];		int j ;	    for(j = i - 1 ; j >=0 && arrays[j] > temp;j--) {			arrays[j+1] = arrays[j];		}		    	    arrays[j+1]= temp;	}}}

希尔排序

public class ShSort {public static void main(String[] args) {	int[] arrays = { 5, 6, 9, 1, 4, 7, 8, 2, 3, 0 };	shSort(arrays);	for (int i = 0; i < arrays.length; i++) {		System.out.println(arrays[i]);	}}public static void shSort(int[] arrays) {		int h = 1;			while(h < (arrays.length/3)) {		h = h+3;	}			while(h > 0) {				int outer;		int inner;					for(outer = h;outer
   
    h-1&&arrays[inner-h]>temp) {				arrays[inner] = arrays[inner-h];				inner -=h;			}			arrays[inner] = temp;		}					h = (h-1)/3;	}		} }

冒泡排序

public class BubbleSort {public static void main(String[] args) {	int[] intArray = {8,8,3,2,7,1,8,5,9,0,4};			long startTime1 = System.currentTimeMillis();	bubbleSorted(intArray);	long endTime1 = System.currentTimeMillis();			System.out.println("排序所话费的时间:::"+ (endTime1 - startTime1)+"ms");		for(int i = 0 ; i < intArray.length ; i++){		System.out.print(intArray[i]);		System.out.println("");	}}	public static void bubbleSorted(int[] intArray) {		boolean needNextPass = true;		//第一次循环只控制循环的次数	for(int i = 1;i < intArray.length;i++) {		needNextPass = false;		//第二层循环开始控制循环次数以及交换数据		for(int j= 0 ; j < intArray.length-i;j++) {			if(intArray[j] > intArray[j+1]) {				int temp = intArray[j];				intArray[j] = intArray[j+1];				intArray[j+1] = temp;				needNextPass = true;			}		}	}	} }

归并排序

public class MergeSort {public static void mergeSort(int[] list) {//至少数组的长度要大于2,才需要进行一份为二。	if(list.length > 1) {	//截取数组的一半	int firstLength = list.length/2;	//new出一个数组	int[] firstArray = new int[firstLength];	//把原始数组的一半值赋值给新的数组。	System.arraycopy(list, 0, firstArray, 0, firstLength);	//然后把新的数组进行分割	mergeSort(firstArray);		//数组的另一半的长度	int secondLength = list.length-(list.length/2);	// new出一个长度为另一半的数组	int[] secondArray = new int[secondLength];	//把原始数组的另一半赋值给新的数组。	System.arraycopy(list, firstLength, secondArray, 0, secondLength);	//对这一半再进行一份为二	mergeSort(secondArray);	 	//开始进行数据的排序	int[] temp = merge(firstArray,secondArray);	System.arraycopy(temp, 0, list, 0, temp.length);			}}public static int[] merge(int[] firstArray,int[] secondArray) {	//新建一个临时数组	int[] temp = new int[firstArray.length+secondArray.length];	int count1 = 0 ;	int count2 = 0 ;	int count3 = 0 ;		while(count1

快速排序

public class QuicklySort {public static void quickSort(int[] list){	quickSort(list,0,list.length-1);}public static void quickSort(int[] list,int first,int last) {	if(last > first) {		int pivotIndex = partition(list,first,last);		quickSort(list,first,pivotIndex-1);		quickSort(list,pivotIndex+1,last);	}}public static int partition(int[] list,int first,int last) {		int pivotValue = list[first];	int low = first + 1;	int high = last;		while(high > low) {				while(low < high && list[high] > pivotValue) {			high--;		}				while(low < high && list[low] <=pivotValue) {			low++;		}				if(high > low) {			int temp = list[high];			list[high] = list[low];			list[low] = temp;		}	}		while(high > low && list[high] >= pivotValue) {		high--;	}		if(list[high] < pivotValue){		list[first] = list[high];		list[high] = pivotValue;		return high;	}else{		return first;	}}		public static void main(String[] args){	int[] list = {2,3,2,5,6,1,-2,3,14,12};	quickSort(list);	for(int i = 0 ; i < list.length ; i ++){		System.out.print(list[i] + " " );	}    } }

堆排序

public class HeapSort {public static 
   
     void heapSort(E[] list) {	Heap
    
      heap = new Heap
     
      ();		for(int i = 0 ; i < list.length;i++) {		heap.add(list[i]);	}			for(int i = list.length-1;i>=0;i--) {		list[i]=heap.remove();	}			}public static void main(String[] args) {	Integer[] list = {2,3,2,5,6,1,-2,3,14,12};	heapSort(list);	for(int i = 0 ; i < list.length;i++) {		System.out.print(list[i]+" ");	}} }public class Heap 
      
       {private java.util.ArrayList
       
         list = new java.util.ArrayList
        
         ();public Heap() { }public Heap(E[] objects) { for(int i = 0 ; i < objects.length;i++) { add(objects[i]); }}public void add(E newObject) { list.add(newObject); //第一步：获取角标，因为角标从零开始，所以要用集合的尺寸减1 int currentIndex = list.size()-1; while(currentIndex > 0) { int parentIndex = (currentIndex-1)/2; if(list.get(currentIndex).compareTo(list.get(parentIndex))>0) { E temp = list.get(currentIndex); list.set(currentIndex, list.get(parentIndex)); list.set(parentIndex, temp); } else { break; } currentIndex = parentIndex; } }public E remove() { if(list.size()==0) { return null; } E removeObject = list.get(0); list.set(0,list.get(list.size()-1)); list.remove(list.size()-1); int currentIndex = 0 ; while (currentIndex < list.size()) { int leftChildIndex = 2*currentIndex+1; int rightChileIndex = 2*currentIndex+2; int size = list.size(); if(leftChildIndex >= size) { //跳出整个while循环。 break; } int maxIndex = leftChildIndex; if(rightChileIndex < size) { if(list.get(maxIndex).compareTo(list.get(rightChileIndex))<0) { maxIndex = rightChileIndex; } } if(list.get(currentIndex).compareTo(list.get(maxIndex))<0) { E temp = list.get(maxIndex); list.set(maxIndex,list.get(currentIndex)); list.set(currentIndex, temp); currentIndex = maxIndex; }else { break; } } return removeObject; }public int getSize() { return list.size();} }