Java排序算法

选择排序

该方法基本原理如下：

1.给定一组数据，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的数据进行交换

2.然后接着对除了第一个数据进行比较，得到最小的记录，与第二个记录进行交换

3.直到比较的记录只有一个为止

以数组 [38 , 65 , 97 , 76 , 13 , 27 , 49] 为例

第一次排序：13 [65 97 76 38 27 49]

第一次排序：13 27 [97 76 38 65 49]

第一次排序：13 27 38 [76 97 65 49]

第一次排序：13 27 38 49 [97 65 76]

第一次排序：13 27 38 49 65 [97 76]

第一次排序：13 27 38 49 65 76[97]

最终排序结果：13 27 38 49 65 76 97

import java.util.Arrays;


public class selectSort {
	
	public static void main(String[] args) {
		int []a=new int[]{38,65,97,76,13,27,49};
		selectSort(a);
		System.out.println(Arrays.toString(a));
	}
	
	public static void selectSort(int []a ){
		//确定最小的数
		int temp=0;
		//下标
		int flag=0;
		for(int i=0;i<a.length;i++){
			temp=a[i];
			flag=i;
			for(int j=i+1;j<a.length;j++){
				if(a[j]<temp){
					temp=a[j];
					flag=j;
				}
			}
			if(flag!=i){
				a[flag]=a[i];
				a[i]=temp;
			}
		}
		
	}

}

插入排序

和选择排序类似，假设第一个记录自成一个有序数列，其余记录皆为无序数列，接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序数列中，直至最后一个记录插入到有序数列中为止。

import java.util.Arrays;
import java.util.Random;


public class insertSort {
	public static void main(String[] args) {
		Random r=new Random();	
		int []a=new int[6];
		for(int i=0;i<a.length;i++){
			a[i]=r.nextInt(9);
		}
		System.out.println(Arrays.toString(a));
		insertSort(a);
		System.out.println(Arrays.toString(a));
	}
	public static void insertSort(int []arr){
		//遍历所有的数字
		for(int i=1;i<arr.length;i++){
			int temp=arr[i];
			int j=i;
			if(arr[j-1]>temp){
				while(j>=1&&arr[j-1]>temp){
					arr[j]=arr[j-1];
					j--;					
				}							
			}
			arr[j]=temp;							
		}
				
	}	
}

冒泡排序

如气泡一样上升，从第一个记录开始，两个相邻的数据依次对比，当前面的记录大于后面的记录时，交换位置，重复到只有一个比较的数为止

import java.util.Arrays;


public class BubbleSort {
	public static void main(String[] args) {
		int [] arr=new int[]{5,7,2,9,1,0,7};
		System.out.println(Arrays.toString(arr));
		bubblesort(arr);
		System.out.println(Arrays.toString(arr));
		
	}
	//比较length-1轮
	public static void bubblesort(int [] arr){
		//控制比较多少轮
		for(int i=0;i<arr.length-1;i++){
			//控制比较的次数
			for(int j=0;j<arr.length-i-1;j++){
				if(arr[j]>arr[j+1]){
					int tmp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=tmp;
				}
			}
					
		}
	}

}

归并排序

import java.util.Arrays;


public class MergeSort {
	public static void main(String[] args) {
		int []a=new int[]{38,65,97,76,13,27,49};
		sort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	
	
	
	
	public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }

}

快速排序

原理

import java.util.Arrays;
import java.util.Random;


public class QuickSort {
	public static void main(String[] args) {
		Random r=new Random();	
		int []a=new int[6];
		for(int i=0;i<a.length;i++){
			a[i]=r.nextInt(9);
		}
		System.out.println(Arrays.toString(a));
		quicksort(a,0,a.length-1);
		
		System.out.println(Arrays.toString(a));			
	}
	public static void quicksort(int[] arr,int start,int end){
		if(start<end){
			//把数组中第0个数字作为标准数	
			int st=arr[start];
			//记录需要排序的下标
			int low=start;
			int high=end;
			//循环找比标准数大的数和比它小的数
			while(low<high){
				//右边的数字比标准数小，高的下标往前移
				while(low<high&&st<=arr[high]){
					high--;
				}
				//使用右边的数字替换左边的数字
				arr[low]=arr[high];
				//如果左边的数字比标准数小
				while(low<high&&arr[low]<=st){
					low++;
				}
				arr[high]=arr[low];						
			}
			//把标准数赋给低的下标所在位置的元素
			arr[low]=st;
			//处理所有小的数字
			quicksort(arr, start,low);
			//处理所有大的数字
			quicksort(arr, low+1,end);
						
		}
		
	}
	
}