首页 > 编程语言 >排序算法

排序算法

时间:2023-04-23 21:23:51浏览次数:36  
标签:sort Sort arr int 算法 排序 public

一、总纲

常见排序算法:冒泡排序(Bubble Sort)、选择排序(Selection Sort)、插入排序(Insertion Sort)、快速排序(Quick Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)、希尔排序(Shell Sort)、计数排序(Counting Sort)、桶排序(Bucket Sort)、基数排序(Radix Sort)

下面是这几种排序算法的Java测试用例:

二、算法实现

1. 冒泡排序(Bubble Sort)

冒泡排序
public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
BubbleSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

2. 选择排序(Selection Sort)

选择排序
 public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
SelectionSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

3. 插入排序(Insertion Sort)

插入排序
 public class InsertionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

4. 快速排序(Quick Sort)

快速排序
 public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            sort(arr, low, pivot - 1);
            sort(arr, pivot + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
QuickSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

5. 归并排序(Merge Sort)

归并排序
 public class MergeSort {
    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int m = 0; m < temp.length; m++) {
            arr[left + m] = temp[m];
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
MergeSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

6. 堆排序(Heap Sort)

堆排序
 public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

7. 希尔排序(Shell Sort)

Shell排序
 public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
ShellSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

8. 计数排序(Counting Sort)

计数排序
 public class CountingSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
CountingSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

9. 桶排序(Bucket Sort)

桶排序
 public class BucketSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        int max = Arrays.stream(arr).max().getAsInt();
        int[] bucket = new int[max + 1];
        for (int i = 0; i < n; i++) {
            bucket[arr[i]]++;
        }
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                arr[index++] = i;
            }
        }
    }
}

// 测试用例
int[] arr = new int[]{3, 9, 1, 4, 7, 8, 5, 6, 2};
BucketSort.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

标签:sort,Sort,arr,int,算法,排序,public
From: https://www.cnblogs.com/maxiaoba/p/17279278.html

相关文章

  • 数据的排序
    1.方法说明: 2.根据指定列进行降序或者升序: 3.根据`数量`和`成交金额`排序: ......
  • 归并排序模板
    voidmerge_sort(intq[],intL,intR){if(L>=R)return;//递归中止条件intmid=(L+R)>>1;merge_sort(q,L,mid);merge_sort(q,mid+1,R);//先递归处理左右intl=L;intr=mid+1;intn=0;while(l<=mid&&......
  • php按照首字母排序,PHP获取汉字首字母并分组排序
    没问题的直接上代码classCharacter{publicfunctiongroupByInitials(array$data,$targetKey='name'){$data=array_map(function($item)use($targetKey){returnarray_merge($item,['initials'=>$thi......
  • #yyds干货盘点# LeetCode程序员面试金典:在排序数组中查找元素的第一个和最后一个位置
    题目:给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回 [-1,-1]。你必须设计并实现时间复杂度为 O(logn) 的算法解决此问题。 示例1:输入:nums=[5,7,7,8,8,10],target=......
  • m基于BP译码算法的QC-LDPC误码率matlab仿真,对比不同译码迭代次数的误码率性能
    1.算法仿真效果matlab2022a仿真结果如下: 2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现......
  • 冒泡排序
    #define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(void){ intarr[4]={1,3,2,'\0'};//加上'\0'后由数组变成字符串 inti,j,temp; for(i=0;i<2;i++) { for(j=0;j<3-i-1;j++) {  if(arr[j]>arr......
  • m基于BP译码算法的QC-LDPC误码率matlab仿真,对比不同译码迭代次数的误码率性能
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道,因此成为编码界近年来的研究热点。它的性能逼近香农极限,且描述和实现简单,易于进行理论分......
  • 操作系统-进程调度算法
      具体功能需求:  (1)数据初始化:数据初始化可通过键盘输入,也可通过构造函数直接生成相应对象。  (2)算法选择功能:程序应向用户提供FCFS、SJ(P)F、优先权算法、时间片轮转算法的选项,由用户键盘输入选择算法,如:   请输入要选择的算法:(0-FCFS;1-SJ(P)F;2-优先权算法;3-时......
  • oracle按身份证号分组后按更新时间排序,取第一条数据
    select  t.*     from (select a.*,row_number() over(PARTITION BY A.IDENTITYCARD order by A.ACCESSIONTIME desc)rn             from T_PATIENT_INFO  a)t    where t.rn= 1 T_PATIENT_INFO--表IDENTITYCARD--证件号码ACC......
  • 三大类算法:递归、排序、二分查找
    一、递归”递“+”归“。这两个意思,正是递归思想的精华所在,去的过程叫做递,回来的过程叫做归,在编程语言中对递归可以简单理解为:方法自己调用自己,只不过每次调用时参数不同而已。满足递归的条件:1、递归表达是(规律)如果一个问题的解能够拆分成多个子问题的解,拆分之后,子问题和该问题在求......