Java程序员面试必备排序算法

20分钟手写6大常考面试排序算法:由于是手写，不耽搁时间，自己练手的，就不写注解了。

1、选择排序

//选择排序
public static void selectSort(int[] arr){

	for(int i = 0;i<arr.length-1;i++){

		for(int j = i+1;j<arr.length;j++){

			if(arr[i] > arr[j]){
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

2、冒泡排序

//冒泡排序
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 temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;

			}
		}
	}
}

3、快速排序（递归+分治）

//快速排序
public static void quickSort(int[] arr,int _left,int _right){

	int left = _left;
	int right = _right;
	int temp = 0;

	if(left <= right){

		temp  = arr[left];

		while(left!=right){

			while(rigth > left && arr[right] >= temp){
				right--;
			}
			arr[left] = arr[right];

			while(left < right && arr[left] <= temp){
				left++;
			}

			arr[right] = arr[left];
		}
		arr[right] = temp;
		quickSort(arr,_left,left-1);
		quickSort(arr,right+1,_right);
	}
}

4、归并排序(递归+分治法)

//归并排序

public static int[] gbSort(int[] arr,int low,int high){

	int mid = (low+high)/2;

	if(low < high){

		gbSort(arr,low,mid);
		gbSort(arr,mid+1,high);
		merge(arr,low,mid,high);
	}

	return arr;
}

public static void merge(int[] arr,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(arr[i] < arr[j]){
			temp[k++] = arr[i++];
		}else {
			temp[k++] = arr[j++];
		}


	}

	while(i<=mid){
		temp[k++] = arr[i++];
	}

	while(j<=high){
		temp[k++] = arr[j++];
	}

	for(int x = 0;x<temp.length;x++){

		arr[x+low] = temp[x];
	}
}

5、插入排序

//插入排序

public static void inserSort(int[] arr){

	int temp = 0;
	for(int i = 1;i<arr.length;i++){

		temp = arr[i];

		for(int j = i-1j>=0;j--){
			if(arr[j]>temp){
				arr[j+1] = arr[j];
			}else{
				break;
			}
		}

	arr[j+1] = temp;
	}

}

6、二分查找

//二分查找
public static void binartSearch(int[] arr,int key){


		int low = 0;
		int high = arr.length-1;

		while(low<=high){

			int mid = (low+high)/2;
			
			if(arr[mid] == key){
				return mid;
			}else if(key < arr[mid]){
				high = mid-1;
			}else{
				low = mid+1;
			}
			return -1;
		}
}

//基数排序
public static void radixSort(int[] arr,int d)
{
    int n=1;//代表位数对应的数：1,10,100...
    int k=0;//保存每一位排序后的结果用于下一位的排序输入
    int length=arr.length;
    int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
    int[] order=new int[length];//用于保存每个桶里有多少个数字
    while(n<d)
    {
        for(int num:arr) //将数组array里的每个数字放在相应的桶里
        {
            int digit=(num/n)%10;
            bucket[digit][order[digit]]=num;
            order[digit]++;
        }
        for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
        {
            if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
            {
                for(int j=0;j<order[i];j++)
                {
                    arr[k]=bucket[i][j];
                    k++;
                }
            }
            order[i]=0;//将桶里计数器置0，用于下一次位排序
        }
        n*=10;
        k=0;//将k置0，用于下一轮保存位排序结果
    }
    
}

//堆排序
//堆排序
 public static void MaxHeapify(int[] a,int index,int size){
    	   int l=2*index;
    	   int r=2*index+1;
    	   int largest=index;
    	   if(l<=size && a[l]>a[index]){
    		   largest=l;
    	   }
    	   if(r<=size && a[r]>a[largest]){
    		   largest=r;
    	   }
    	   if(largest!=index){
    		   int temp=a[largest];
    		   a[largest]=a[index];
    		   a[index]=temp;
    		   MaxHeapify(a,largest,size);
    	   }
       }
       public static void HeapBuild(int[] a,int size){
    	   for(int i=size/2;i>=1;i--){
    		   MaxHeapify(a,i,size);
    	   }
       }
       public static void Sort(int[] a,int size){
    	   HeapBuild(a,size);
    	   for(int i=size;i>=2;i--){
    		   int temp=a[i];
    		   a[i]=a[1];
    		   a[1]=temp;
    		   MaxHeapify(a,1,i-1);
    	   }
       }

手写不易，且赞且珍惜！