排序算法总结

桶排序

取另外一个数组进行记录该排序数组中的出现次数，该数组初始的所有值都为0，当排序数组中的数在0~n时，就需要n+1长度为n+1的数组进行记录。桶排序是利用该数组的下标进行记录排序数组的出现次数，下标就表示值，当整个排序数组都被记录后，就遍历该数组，打印出该下标值。这样就排序出该数组了。 缺点：需要另外的数组开销大，且只适用用正整数的情况

 Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt(); 
        
        int[] array=new int[10001];
        
        for(int j=0;j<=10000;j++){
            array[j]=0;
            
        }
        
        for(int i=1;i<=n;i++){
            
            int num=sc.nextInt();
            array[num]+=1;
        }
                
        for(int len=1;len<=10000;len++){
            for(int count=1;count<=array[len];count++){


                System.out.print(len+" ");
            }

冒泡排序

每次总是与相邻位置的数据进行比较，当下一个数比它小时 ，就交换位置，第一轮结束后，就把最大的数排到最后的位置上了，然后进行下一轮的比较，接着就把倒数第二大的数排到倒数第二的位置上去了，以此类推，就把所有的数排序好了。长度为n的数组只需要n-1次比较 缺点：时间复杂度高

 //冒泡排序：n个数排序，只需要n-1次轮回比较
        //注意内部次数的界限

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

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

                if(array[p]>array[p+1]){

                    int temp=array[p+1];
                    array[p+1]=array[p];
                    array[p]=temp;

                }

            }
        }

选择排序

与冒泡排序类似，但不是只和相邻的数进行比较，而是依次与后面的数进行比较，然后交换位置。长度为n的数组只需要n-1次比较 缺点：时间复杂度高

 //选择排序
        for(int i=0;i<array.length-1;i++){

            for(int p=i;p<array.length;p++){
                 if(array[i]>array[p]){

                    int temp=array[i];
                    array[i]=array[p];
                    array[p]=temp;

                }

            }
        }

快速排序

需要定义一个基数，然后把数组中大于这个数的排在右边，小于这个数的排在左边。 方法：定义两个指针，左指针指向数组的头部，右指针指向数组的尾部，基数选取最左边的第一个数。每次都是右指针开始向中间移动，右指针只要没遇到比他（基数）小的数就一直向前移动，当遇到比他（基数）小的数就停止移动，然后左指针开始移动，只要左指针没有遇到比他大的数就一直向前移动，遇到后就停止移动，然后交换左右指针的值，只要左右指针没有指向同一个数，就一直重复上述步骤，当左右指针遇到同一个值后，就交换这个值与基数的位置，然后以基数为分割点递归处理左右两边的值，一旦左指针大与右指针就停止递归，意味着排序完成

题目推荐 215. ***********

public static void quicksort(int[] array,int left,int right){
      
      
       //判断是否终止
        if(left>right){
            return;
        }

         //定义基准数
        int base=array[left];

        //这里的ij表示新的移动值，二而left，right表示旧的值
        int i=left;
        int j=right;

        while(i!=j){

            //右指针向中间移动,右指针寻找小于基准数的值才跳出循环

            while(array[j]>=base && i<j){
                j--;


            }


            //左指针向中间移动，左指针寻找大于基准数的值才跳出循环
            while(array[i]<=base && i<j){
                i++;


            }

            //交换两个指针的值
            if(i<j){

                int temp=array[j];
                array[j]=array[i];
                array[i]=temp;



            }

        }
        //当一轮交换结束后，即左右指针相等。就交换基准数和共同指针的值
        array[left]=array[i];
        array[i]=base;


        //操作左边的值
        quicksort(array,left,i-1);
        //操作右边的值
        quicksort(array,i+1,right);



    } 

归并排序

采用分治的思想，不断将要排序的数组的进行拆分，直到 拆分成一个个子元素，然后再不断地将子元素进行合并排序，如要求从小到大排序，再合并的时候，就要求小的在前，大的在后，直到最后 合并的元素的长度等于之前的长度。

题目推荐
*************************
合并两个有序的数组_牛客题霸_牛客网 (nowcoder.com)

public class mergeSort{

	static int[] temp;

	public static void main(Stirng[] args){
		int[] nums={};

		temp=new int[nums.length];
		Sort(nums,0,nums.length-1);

	}


	public void Sort(int nums,int left,int right){
		if(left==right){
			return ;//递归终止条件
		}

		int mid=left+((right-left)>>1);

		Sort(nums,left,mid);//拆分左区间
		Sort(nums,mid+1,right);//拆分右区间

		merge(nums,left,mid,right);


	}


	public static void merge(int nums,int left,int mid,int right){


		//暂存区间的值，用于比较

		for(int i=left;i<=right;i++){
			temp[i]=nums[i];
		}

		int index1=left;
		int index2=mid+1;

		for(int i=left;i<=right;i++){

				if(index1==mid+1){
					nums[i]=temp[index2++];//只剩下右边
				}else if(index2=right+1){
					nums[i]=temp[index1++];//只剩下左边
				}else if(temp[index1]<temp[index2]){
					nums[i]=temp[index1++];
				}else{
					nums[i]=temp[index2++];
				}

		}



	}
}