排序算法学习笔记（二）

àì夳堔傛蜴生んèń 2023-09-29 13:21 12阅读 0赞

**目录**

一：快速排序

二：归并排序

--------------------

## 一：快速排序 ##

**1.1 基本思想：**

> [快速排序][Link 1]是我们之前学习的冒泡排序的升级，他们都属于交换类排序，都是采用不断的比较和移动来实现排序的。快速排序是一种非常高效的排序算法，它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动次数。同时采用“分而治之”的思想，把大的拆分为小的，小的拆分为更小的，其原理如下：对于给定的一组记录，选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到序列中的所有记录均有序为止。

**1.2 思路分析：**

![3534045b3f5e48d9921a47b67a14d917.png][]

**1.3 快速排序代码实现：**

package package03;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int N=sc.nextInt();
            int[] arr=new int[N];
            for(int i=0;i<arr.length;i++){
                arr[i]=sc.nextInt();
            }
            quickSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
    
        }
        public static void quickSort(int[] arr,int left,int right){
            int l=left-1;
            int r=right+1;
            int temp;
            int pivot=arr[(left+right)/2];//中轴值
            while (l<r){
    
                do{
                    l++;
                }while (arr[l]<pivot);
                do{
                    r--;
                }while (arr[r]>pivot);
    
                if(l==r){//该中轴值的左边均小于中轴值，右边均大于中轴值，使得下标都指向中轴值
                    break;
                }
    
                //交换
                if(l<r){
                    temp=arr[l];
                    arr[l]=arr[r];
                    arr[r]=temp;
                }
    
            }
            if(l>left){
                quickSort(arr,left,l-1);
            }
            if(r<right){
                quickSort(arr,r+1,right);
            }
    
        }
    }

## 二：归并排序 ##

**2.1 归并排序的概念：**

> 归并排序采用的是[分治][Link 2](divide-and-conquer)法思想。

**2.1.1**）基本思想：将待排序元素分成大小大致相同的2个子[集合][Link 3]，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

**2.1.2**）执行过程：

![9e818910da7e4d56aa1325be05590d28.png][]

![c9a7991d8f464e2b89ee7ab32eb88574.png][]

import java.util.Scanner;
    
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int N=sc.nextInt();
            int[] arr=new int[N];
            for(int i=0;i<N;i++){
                arr[i]=sc.nextInt();
            }
            int[]temp=new int[N];   //中间数组
            mergeSort(arr,0, arr.length-1,temp);
            for(int i=0;i<arr.length;i++){
                System.out.print(arr[i]+" ");
            }
    
        }
        //分+和的方法：
        public static void mergeSort(int[] arr,int left,int right,int[] temp){
    
            if(left<right){
                int mid=(left+right)/2;
                mergeSort(arr,left,mid,temp);//对左端数组进行递归拆开
                mergeSort(arr,mid+1,right,temp);//对右端数组进行递归拆开
                merge(arr,left,mid,right,temp);
            }
        }
        //合并数据
        public static void merge(int[] arr,int left,int mid,int right,int[] temp){
            int i=left;//左端数组最开始的索引，数组范围：[left,mid]
            int j=mid+1;//右端数组最开始的索引，数组范围：[mid+1,right]
            int k=0;//临时数组temp最开始的索引
            while (i<=mid&&j<=right){
                if(arr[i]<=arr[j]){
                    temp[k++]=arr[i++];
                }else {
                    temp[k++]=arr[j++];
                }
            }
    
            //左端数组或右端数组可能存在数据剩余，需要将剩余数据传入temp数组中
            while (i<=mid){
                temp[k++]=arr[i++];
            }
            while (j<=right){
                temp[k++]=arr[j++];
            }
    
            //将temp数组中的数据传入arr数组
            for(int u=0;u<k;u++){
                arr[left+u]=temp[u];//这里需要加上left，因为不是每一次都是从0开始合并数据的
            }
    
        }
    }

--------------------

[Link 1]: https://so.csdn.net/so/search?q=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&spm=1001.2101.3001.7020
[3534045b3f5e48d9921a47b67a14d917.png]: https://img-blog.csdnimg.cn/3534045b3f5e48d9921a47b67a14d917.png
[Link 2]: https://so.csdn.net/so/search?q=%E5%88%86%E6%B2%BB&spm=1001.2101.3001.7020
[Link 3]: https://so.csdn.net/so/search?q=%E9%9B%86%E5%90%88&spm=1001.2101.3001.7020
[9e818910da7e4d56aa1325be05590d28.png]: https://img-blog.csdnimg.cn/9e818910da7e4d56aa1325be05590d28.png
[c9a7991d8f464e2b89ee7ab32eb88574.png]: https://img-blog.csdnimg.cn/c9a7991d8f464e2b89ee7ab32eb88574.png