几种排序算法简单的回顾(Java实现)

1.简单的回顾一下排序算法。发现写代码的时候还是有很多错误的地方。
2.附上简单的图片说明和代码。(网图侵删)
3.代码在本地运行均已通过。
==========================================================
1.冒泡排序(Bubble Sort)
2.插入排序(Insertion Sort)
3.选择排序(Selection Sort)
4.希尔排序(Shell Sort)
5.归并排序(Merge Sort)
6.快速排序(Quick Sort)
7.桶排序(Bucket Sort)
8.基数排序(Radix Sort)
9.计数排序(Counting Sort)
10.堆排序(Heap Sort)

1.冒泡排序(Bubble Sort)

 public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7};
        BubbleSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
    static void BubbleSort(int[] nums, int n) {
   
        for (int i = 0; i < n; i++) {
   
            boolean flag = false;//若无交换退出
            for (int j = 0; j < n - i - 1; j++)
                if (nums[j] > nums[j + 1]) {
   
                    int index = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = index;
                    flag = true;
                }
            if (!flag)
                break;
        }
    }

2.插入排序(Insertion Sort)

// A code block
var foo = 'bar';

public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        InsertionSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
    static void InsertionSort(int[] nums, int n) {
   
        if (n == 1)
            return;
        for (int i = 1; i < n; i++) {
   
            int index = nums[i];
            int j = i - 1;
            for (; j >= 0; j--) {
   
                if (nums[j] > index) {
   //进行移位操作
                    nums[j + 1] = nums[j];

                } else {
   
                    break;
                }
            }
            nums[j + 1] = index;//插进去
        }
    }

3.选择排序(Selection Sort)

public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        SelectionSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
    static void SelectionSort(int[] nums, int n) {
   
        for (int i = 0; i < n - 1; i++) {
   
            int index = i;
            for (int j = i + 1; j < n; j++)//选择最小的
                if (nums[j] < nums[index])
                    index = j;
                //交换
            int temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
        }
    }

4.希尔排序(Shell Sort)

public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        ShellSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
static void ShellSort(int[] A, int n) {
   
        if (A == null || n < 2)
            return;
        for (int gap = n / 2; gap > 0; gap /= 2) {
   
            for (int i = gap; i < n; i++) {
   
                S(A, gap, i);
            }
        }
        return;
    }
static void S(int[] A, int gap, int i) {
   
        int k = 0;
        int index = A[i];
        for (k = i - gap; k >= 0 && index < A[k]; k -= gap) {
   
            A[k + gap] = A[k];
        }
        A[k + gap] = index;
    }

5.归并排序(Merge Sort)

 public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        //int[] nums = {2, 1};
        MergeSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
static void MergeSort(int[] nums, int left, int right) {
   
        if (left < right) {
   
            int index = (left + right) / 2;
            MergeSort(nums, left, index);
            MergeSort(nums, index + 1, right);
            Merge(nums, left, index, right);
        }
    }
static void Merge(int[] A, int left, int index, int right) {
   
        int[] B = new int[right - left + 1];
        int i = left;
        int j = index + 1;
        int k = 0;
        //1.两两进行比较，融合
        while (i <= index && j <= right) {
   
            if (A[i] <= A[j]) {
   
                //前面小于后面那就不用换
                B[k++] = A[i++];
            } else {
   
                B[k++] = A[j++];
            }
        }
        //2.判断哪边还有剩余的
        while (i <= index) B[k++] = A[i++];
        while (j <= right) B[k++] = A[j++];
        //3.导入原数组
        for (i = 0; i < k; i++) {
   
            A[left++] = B[i];
        }
    }

6.快速排序(Quick Sort)

public static void main(String[] args) {
   
        //int[] nums = {9, 5, 2, 7, 1, 0, 0};
        int[] nums = {
   9, 5, 2, 7};
        QuickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
static void QuickSort(int[] A, int left, int right) {
   
        if (left >= right)
            return;
        //得到把两边分开的那个数的下标
        int index = Q(A, left, right);
        QuickSort(A, left, index - 1);
        QuickSort(A, index + 1, right);
    }
static int Q(int[] A, int left, int right) {
   
        int J = A[left];
        int start = left;
        int end = right;
        while (start != end) {
   
        //1.数很大就往回退
            while (start < end && A[end] > J) {
   
                end--;
            }
         //2.数很小就往前冲
            while (start < end && A[start] <= J) {
   
                start++;
            }
            if (start < end) {
   //3.交换
                int t = A[start];
                A[start] = A[end];
                A[end] = t;
            }
        }
        int t = A[left];//4.移动那个用来比较的数
        A[left] = A[start];
        A[start] = t;
        return start;
    }

7.桶排序(Bucket Sort)

public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        BucketSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
static void BucketSort(int[] A, int n) {
   
        if(A==null||n<2)
            return;
        int max=A[0];
        int min=A[0];
        int l;
        int Tcount;//桶的数量
        int j=0;
        for (int i = 1; i < n; i++) {
   
            if(max<A[i])
                max=A[i];
            if(min>A[i])
                min=A[i];
        }
        //1.创建并且初始化
        l=max-min;
        Tcount=l/2+1;//防止范围过大
ArrayList<LinkedList<Integer>> T=new ArrayList<>(Tcount);
        for (int i = 0; i < Tcount; i++) {
   
            //2.每个桶中都是链表
            T.add(new LinkedList<Integer>());
        }
        //3.确认放入哪个桶
        for (int i = 0; i < n; i++) {
   
            //4.(A[i]-min)/l决定放入哪个桶,及以数列的最小下标作为偏移量
            T.get((A[i]-min)/l).add(A[i]-min);
        }
        for (int i = 0; i < Tcount; i++) {
   
            Collections.sort(T.get(i));
        }

        for (int i = 0; i < Tcount; i++) {
   
            System.out.println(T.get(i).toString());
            for(Integer t:T.get(i)){
   
                A[j++]=min+t;
            }
        }
        return ;
    }

8.基数排序(Radix Sort)

public static void main(String[] args) {
   
        int[] nums = {
   91, 55, 22, 79, 14, 10, 80};
        RadixSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

static void RadixSort(int[] A, int n) {
   
        if (A == null || n < 2)
            return;
        int max = A[0];//1.取最大值，看有多少位
        int Tcount = 0;
        for (int i = 1; i < n; i++) {
   
            if (A[i] > max)
                max = A[i];
        }
        while (max > 0) {
   
            Tcount += 1;
            max = max / 10;
        }
        //2.按照十个下标，创建十个桶
ArrayList<LinkedList<Integer>> T = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
   
            T.add(new LinkedList<Integer>());
        }
        //3.从个位开始到最后排，依次进行
        for (int i = 1; i <= Tcount; i++) {
   
            for (int j = 0; j < n; j++) {
   
                //返回获取每个数第i位
                int q = (A[j] / (int) Math.pow(10, i - 1)) % 10;
                T.get(q).add(A[j]);
            }
            //4.将伪排好的放回原数组
            int k = 0;
            int j;
            for (j = 0; j < 10; j++) {
   
                for (Integer t : T.get(j)) {
   
                    A[k++] = t;
                }
                T.get(j).clear();
            }
        }
        return;
    }

9.计数排序(Counting Sort)

1.统计个数

2.累加过程

3.排序

public static void main(String[] args) {
   
        // int[] nums = {9, 5, 2, 7, 1, 0, 0};
        int[] nums = {
   1, 0, 0};
        CountingSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
static void CountingSort(int[] A, int n) {
   
        if (n <= 1)
            return;
        int max = A[0];
        //找出最大的数，以确定要开辟多大数组
        //针对范围不是太大的数组
        //若范围过大可使用最小数进行偏移
        for (int i = 1; i < n; i++) {
   
            if (max < A[i])
                max = A[i];
        }
        int[] C = new int[max + 1];
        //1.统计每个元素的个数
        for (int i = 0; i < n; i++) {
   
            C[A[i]] += 1;
        }
        //2.累加
        for (int i = 1; i <= max; i++) {
   
            C[i] = C[i] + C[i - 1];
        }
        int[] Lin = new int[n];
        //3.从后往左遍历原数组
        for (int i = n - 1; i >= 0; i--) {
   
            int k = C[A[i]] - 1;//4.k决定了A[i]要排在临时数组哪个位置
            Lin[k] = A[i];//5.付给临时数组
            C[A[i]]--;//6.减去1，以防下次再遇到相同的A[i]
        }
        for (int i = 0; i < n; i++) {
   
            A[i] = Lin[i];
        }
    }

10.堆排序(Heap Sort)

public static void main(String[] args) {
   
        int[] nums = {
   9, 5, 2, 7, 1, 0, 0};
        // int[] nums = {1, 0, 0};
        HeapSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }
 static void HeapSort(int[] A, int n) {
   
        //1.首先要构建堆
        //2.从最后一个非叶子节点开始下沉
        for (int i = (n - 2) / 2; i >= 0; i--) {
   
            Down(A, i, n - 1);
        }//构建完毕。
        //3.开始排序，把大的放到最后
        for (int i = n - 1; i >= 0; i--) {
   
            int index = A[i];
            //A[0]通过调整总是最大的
            A[i] = A[0];
            A[0] = index;
            //0为父节点
            Down(A, 0, i - 1);
        }
    }
static void Down(int[] A, int parent, int n) {
   
        int index = A[parent];
        //左孩子加1，右孩子加2
        int child = 2 * parent + 1;
        while (child <= n) {
   
            //左右孩子的比较，找那个大的交换。因为小放在上边
            if (child + 1 <= n && A[child] < A[child + 1])
                child++;
            if (A[child] <= index)
                break;
            A[parent] = A[child];
            parent = child;//看继续还能不能下沉
            child = 2 * parent + 1;
        }
        A[parent] = index;
    }

11.复杂度

若有错误还请指正。

转载：https://blog.csdn.net/qq_43820953/article/details/115522097