sort

Posted on 2021-12-07 Edited on 2021-12-08

AP CSA Sorting Algorithms

没想到AP CSA居然也涉及排序的内容本篇就分享几种基本的排序算法以及JAVA代码实现

Content:

Bubble Sort
Insert Sort
Select Sort
Quick Sort
Bucket Sort

Bubble Sort

一种简单但是十分低效的算法。在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一轮比较中：首先比较第1个和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一轮的步骤，直至全部排序完成。如果能看到算法可视化的话，就可以看到小的数像气泡一样，一点一点的从下面浮上来，所以叫bubble sort，冒泡排序。

Java 实现:

import java.util.*;
public class BubbleSort{
    public static void main(String[] agrs){
        Scanner scan=new Scanner(System.in);
        System.out.println("Enter numbers of elements: ");
        int n=scan.nextInt();
        int[] a=new int[n+5];
        for(int i=0;i<n;i++){
            a[i]=scan.nextInt();
        }
        /*
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]>a[j]){
                    int ins=a[i];
                    a[i]=a[j];
                    a[j]=ins;
                }
            }
        }
        */
        for(int i=0;i<n;i++){
            for(int j=n-2;j>=i;j--){
                if(a[j]>a[j+1]){
                    int ins=a[j];
                    a[j]=a[j+1];
                    a[j+1]=ins;
                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

Insert Sort

把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列


import java.util.*;
public class InsertSort{
    public static void main(String[] agrs){
        Scanner scan=new Scanner(System.in);
        System.out.println("Enter numbers of elements: ");
        int n=scan.nextInt();
        int[] a=new int[n+5];
        for(int i=0;i<n;i++){
            a[i]=scan.nextInt();
        }
        for(int i=0;i<n;i++){
            int std=a[i];
            int j;
            for(j=i-1;j>=0;j--){
                if(a[j]>std){
                    a[j+1]=a[j];
                }
                else{
                    break;
                }
            }
            a[j+1]=std;
        }
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

Select Sort

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

import java.util.*;
public class SelectSort{
    public static void main(String[] agrs){
        Scanner scan=new Scanner(System.in);
        System.out.println("Enter numbers of elements: ");
        int n=scan.nextInt();
        int[] a=new int[n+5];
        for(int i=0;i<n;i++){
            a[i]=scan.nextInt();
        }
        for(int i=0;i<n;i++){
            int flag=i;
            for(int j=i+1;j<n;j++){
                if(a[j]<a[flag]){
                    flag=j;
                }
            }
            int ins=a[i];
            a[i]=a[flag];
            a[flag]=ins;
        }
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

Quick Sort

也就是常说的快速排序，综合上来讲最快也是最好的排序算法之一，记住别爆栈。

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一轮扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到各区间只有一个数。

import java.util.*;
public class QuickSort{
    static int[] a=new int[10000000];
    public static void quickSort(int[] a, int left, int right){
        int std=a[left];
        int i=left,j=right;
        if(right<=left){
            return;
        }
        else{
            while(i<j){
                while(j>i&&a[j]>std){
                    j--;
                }
                if(i<j){
                    a[i]=a[j];  
                    i++;
                }
                while(i<j&&a[i]<=std){
                    i++;
                }
                if(i<j){
                    a[j]=a[i];
                    j--;
                }
            }
            a[i]=std;
            quickSort(a,left,i-1);
            quickSort(a,i+1,right);
        }
    }
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        System.out.println("Enter numbers of elements: ");
        int n=scan.nextInt();
        for(int i=0;i<n;i++){
            a[i]=scan.nextInt();
        }
        quickSort(a,0,n-1);
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

Bucket Sort

桶排序最典型的空间换时间的例子

import java.util.*;
public class BucketSort{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        System.out.println("Enter numbers of elements: ");
        int n=scan.nextInt();
        int[] a=new int[10000005];
        for(int i=0;i<n;i++){
            a[scan.nextInt()]++;
        }
        for(int i=0;i<10000005;i++){
            if(a[i]==0){
                continue;
            }
            else{
                for(int j=0;j<a[i];j++){
                    System.out.print(i+" ");
                }
            }
        }
        System.out.println();
    }
}

Sources&References

https://www.cnblogs.com/zwtgyh/p/10631760.html https://blog.csdn.net/left_la/article/details/8656425 https://www.cnblogs.com/zwb2jcy/p/9110676.html https://blog.csdn.net/qq_38790716/article/details/85929469 https://blog.csdn.net/qq_36770641/article/details/82669788