Java实现五种主要排序的算法

1,冒泡法：


　　public class BubbleSortImpl1 {
　　public static void BubbleSort(int A[]) {
　　int n = A.length;
　　for(int i=0;i 
　　for(int j=0;j 
　　if(A[j]>A[j+1])
　　{
　　int temp=A[j];
　　A[j]=A[j+1];
　　A[j+1]=temp;//直接调用Swap会出错。why?
　　}
　　}
　　}
　　}
　　public static void swap(int a, int b) {
　　int temp = a;
　　a = b;
　　b = temp;
　　}
　　/**
　　* @param args
　　*/
　　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　int A[] = new int[] { 2, 5, 3, 9, 7, 1, 30 };
　　BubbleSort(A);
　　for (int i = 0; i < A.length; i++) {
　　System.out.println(A);
　　}
　　}
　　}


　　2，堆排序

　


　　public class HeapSort {
　　static void HeapAdjust(int H[],int s,int n){//使H[s...m]称为一个大顶堆
　　int rc=H[s];
　　int j;
　　for(j=2*s;j<=n;j=j*2){
　　if(j 
　　++j;//j为父节点的最大孩子
　　if(rc>=H[j])
　　break;//rc应该掺入在j的父位置上
　　H[s]=H[j];//j上移
　　s=j;
　　}
　　H[s]=rc;
　　}
　　static void Heap_Sort(int H[]){
　　int n=H.length;
　　for(int i=n/2;i>0;i--){
　　HeapAdjust(H,i,n);
　　}//
　　for(int k=n-1;k>1;k--){
　　int temp=H[1];
　　H[1]=H[k];
　　H[k]=temp;//将堆顶记录和 当前未经排序子序列中最后一个记录交换。
　　HeapAdjust(H,1,k-1);
　　}
　　}
　　/**
　　* @param args
　　*/
　　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　int A[]={0,3,5,9,2,7};
　　Heap_Sort(A);
　　for(int i=0;i 
　　System.out.print(A);
　　}
　　}

　　3，插入排序


　　public class InsertSortImpl {
　　/**
　　* @param args
　　*/
　　public static void InsertSort(int A[]) {
　　int n = A.length;
　　for (int i = 0; i < n-1; i++) {
　　int temp = A[i+1];
　　Insert(A, temp, i );
　　}
　　}
　　public static void Insert(int A[], int e, int k) {// 对A[1...k]排序
　　while(k>=0&&A[k]>e){
　　A[k+1]=A[k];
　　k--;
　　}
　　A[k+1]=e;
　　}
　　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　int A[] = new int[] { 2, 5, 3, 9, 7, 1, 30,6 };
　　InsertSort(A);
　　for (int i = 0; i < A.length; i++) {
　　System.out.println(A);
　　}
　　}
　　}


　　4，快速排序

　　


import java.util.Random;
　　public class QuickSortImpl {
　　/**
　　* @param args
　　*/
　　public static void swap(int a, int b) {
　　int temp = a;
　　a = b;
　　b = temp;
　　}
　　public static void QuickSort(int A[], int left, int right) {
　　if (left < right) {
　　int i = left;
　　int j = right;
　　int pivot = A[left];
　　while(left 
　　while(A[left] 
　　++left;
　　}
　　while(A[right]>pivot){
　　--right;
　　}
　　if(left 
　　int temp=A[left];
　　A[left]=A[right];
　　A[right]=temp;
　　}
　　}
　　int temp=A[right];
　　A[right]=pivot;
　　pivot=temp;
　　QuickSort(A, i, right- 1);
　　QuickSort(A, right+1, j);
　　}
　　}
　　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　int A[]=new int[]{3,7,2,35,8,9};
　　QuickSort(A,0,5);
　　for(int i=0;i<5;i++){
　　System.out.println(A);
　　}
　　}
　　}


　　5，选择排序

　
　　public class SortedSortImpl {
　　public static void SelectSort(int A[]) {// 通过n-i此关键字比较，从
　　// n-i+1个记录中选出最小的与第i个记录交换
　　int n = A.length;
　　for (int i = 0; i < n; i++) {
　　int k = i;
　　for (int j = i + 1; j < n; j++) {
　　if (A[k] > A[j]) {
　　k = j;
　　}
　　}
　　int temp = A;
　　A = A[k];
　　A[k] = temp;
　　}
　　}
　　/**
　　* @param args
　　*/
　　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　int A[] = new int[] { 2, 5, 3, 9, 7, 1, 30 };
　　SelectSort(A);
　　for (int i = 0; i < A.length; i++) {
　　System.out.println(A);
　　}
　　}
　　}