投稿
  1. 首页
  2. 随笔

使用Java实现各种排序算法

ccer • 2022-12-18 • 随笔 • 阅读 30

使用Java实现各种排序算法,第1张

使用Java实现各种排序算法 排序基本概念

基本概念：所谓排序，即将原本无序的序列重新排列成有序序列的过程。这个序列中的每一项可能是单独的数据元素，也可能是一条记录（记录是由多个数据元素组成的，如一个学生记录就是学号、姓名、年龄、专业等数据元素组成的）。如果是记录，则既可以按照记录的主关键字排序（主关键字唯一标识一条记录，如学生记录中的学号就是主关键字，学号不能重复，用来唯一标识一个学生），也可以按照记录的次关键字排序（如学生记录中的姓名、专业等都是次关键字，次关键字是可以重复的）。

排序的分类 插入类算法 1. 直接插入排序

外层for循环从前往后，内层while循环将此处数值插到前面已排序的序列中，将数据依次向后挪动一位。
代码：

public void InsertSort(int[] arr, int n){
        int temp;
        int j;
        for (int i = 1; i < n; i++) {
            temp = arr[i]; //将待插入关键字暂存到temp中
            j = i-1;
            while (j >= 0 && temp < arr[j]){ //j>=0为了防止超出数组前部界限
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp; //找到插入位置，将temp中暂存的待排序关键字插入
        }
    }
2. 折半插入排序

折半插入排序（Binary Insertion Sort）的思想和直接插入排序的思想类似，区别就是查找插入位置的方式不同，折半插入排序是采用折半查找法来查找位置的。折半查找法的一个基本条件是序列已经基本有序，即如同直接插入排序一样已排序列有序，在有序序列使用折半查找法中找出待插入关键字的位置。
代码：

public void BInsertSort(int[] arr, int n){
        int low, mid, high;
        int temp;
        for (int i = 1; i < n; i++) {
            low = 0;
            high = i-1;
            temp = arr[i];
            while(low <= high){
                mid = (low+high)/2;
                if (temp > arr[mid]) low = mid+1;
                else high = mid-1;
            }
            for (int j = i-1; j > high; j--) {
                arr[j+1] = arr[j];  //high+1到i-1的关键字向后移一位
            }
            arr[high+1] = temp; //待插入关键字插入到high后面一位
        }
    }
3. 希尔排序

希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将排序序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。
增量选择规则一般有下面两种：
1）希尔自己提出的：
⌊n/2⌋、⌊n/4⌋、……、⌊n/2^k⌋、……、2、1
即每次将增量除以2向下取整，其中n为序列长度，此时时间复杂度为O(n^2)。
2) 帕佩尔诺夫和斯塔舍维奇提出的：
2^k+1、……、65、33、17、9、5、3、1
其中，k为大于等于1的整数，2^k+1小于待排序序列的长度，增量序列末尾的1是额外添加的，此时时间复杂度为
O(n^1.5)
代码：

public void ShellSort(int[] arr, int n){
        int temp;
        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                temp = arr[i];
//                两种循环（for和while）均可实现子序列的排序
//                int j;
//                for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) arr[j] = arr[j-gap];
                int j = i;
                while (j >= gap && arr[j-gap] > temp) {
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
交换类排序 1. 起泡（冒泡）排序

外层for循环从后往前，内层循环从前往后依次将最大数值轮到序列末尾
代码：

public void BubbleSort(int[] arr, int n){ //改进的冒泡排序
        int temp;
        int flag;
        for (int i = n-1; i >= 1 ; i--) {
            flag = 0; //变量flag用来标记本趟排序是否发生了交换
            for (int j = 1; j <= i; j++) {
                if (arr[j-1] > arr[j]){
                    flag = 1;  //如果发生了交换，flag置为1
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
            if (flag == 0) { //则证明序列有序，排序结束
                return;      //一趟排序过程中没有发生关键字交换
            }
        }
    }
2. 快速排序

设置两个“指针”：low&high. 分别指向数组首部和尾部，从尾部开始进行while循环，遇到比枢轴（通常是第一个关键字）大的就一直j–向左移动，直到碰到比枢轴小的关键字，移到序列左端，即此时i所在位置，再开始从首部开始的while循环，也是同样的方法，两个循环交替进行，直到i = j为止。
代码：

public void QuickSort(int[] arr, int low, int high){
        int temp;
        int i = low;
        int j = high;
        if (i < j){
            temp = arr[low];
            while (i < j){
                while (i < j && temp <= arr[j]) j--;
                if (i < j){
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && temp >= arr[i]) i++;
                if (i < j){
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = temp;
            QuickSort(arr,low,i-1);
            QuickSort(arr,j+1,high);
        }
    }
选择类排序 1. 简单选择排序

外层for循环从前往后遍历，内层for循环从剩下的无序序列中选出最小关键值的序号，然后与此处的数值交换。
代码：

public void SelectSort(int[] arr,int n){
        int temp;
        int k;
        for (int i = 0; i < n; i++) {
            k = i;
            
            for (int j = i+1; j < n; j++) {
                if (arr[k] > arr[j]) {
                    k = j;
                }
            }
            if(k != i){
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
            
        }
    }
2. 堆排序

堆是一种数据结构，堆排序中最关键的 *** 作是将序列调整成堆。
执行过程：
1）建堆
先将序列调整成一个大顶堆。需要满足完全二叉树的性质。
2）插入节点
需要在插入节点后保持堆的性质。
3）删除节点
当删除堆中一个节点时，把最底层最右边的叶子的值赋给此位置并调到合适的位置，最后把叶子删除。
4）排序：取出建立好的大顶堆第一个关键字（根节点），

二路归并排序

归并排序 可以看作是一个分而治之的过程，先将两个序列分为两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。一半用low和high两整型变量代表需要进行归并排序的关键字范围。
代码：

public void merge(int[] arr, int low, int mid, int high){
        int n1 = mid-low+1;
        int n2 = high-mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[low+i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid+j+1];
        }
        int i = 0;int j = 0;
        int k = low;
        while (i < n1 && j < n2){
            if(L[i] <= R[j]){
                arr[k++] = L[i++];
            }
            else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1){
            arr[k++] = L[i++];
        }
        while (j < n2){
            arr[k++] = R[j++];
        }
    }
    public void mergeSort(int[] arr, int low, int high){
        if(low < high){
            int mid = (high+low)/2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }
基数排序

基数排序的思想是“多关键字排序”。本篇使用 最低位优先 方法实现基数排序，即每次根据从低位开始进行“分配”和“收集”。
代码：

public void countingSort(int[] arr, int place) {
        int size = arr.length;
        int[] output = new int[size];
        // 假设第一个元素指定数位上的值最大
        int max = (arr[0] / place) % 10;
        // 找到真正数位上值最大的元素
        for (int i = 1; i < size; i++) {
            if (((arr[i] / place) % 10) > max)
                max = (arr[i] / place) % 10;
        }
        // 创建并初始化 count 数组
        int[] count = new int[10];
        for (int i = 0; i < 10; ++i)
            count[i] = 0;
        // 统计各个元素出现的次数
        for (int i = 0; i < size; i++)
            count[(arr[i] / place) % 10]++;
        // 累加 count 数组中的出现次数
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        // 根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
        for (int i = size - 1; i >= 0; i--) {
            output[count[(arr[i] / place) % 10] - 1] = arr[i];
            count[(arr[i] / place) % 10]--;
        }
        // 将 output 数组中的数据原封不动地拷贝到 arr 数组中
        for (int i = 0; i < size; i++)
            arr[i] = output[i];
    }
    // 找到整个序列中的最大值
    public int getMax(int[] arr) {
        int size = arr.length;
        int max = arr[0];
        for (int i = 1; i < size; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }

    public void radixSort(int[] arr) {
        // 找到序列中的最大值
        int max = getMax(arr);
        // 根据最大值具有的位数，从低位依次调用计数排序算法
        for (int place = 1; max / place > 0; place *= 10)
            countingSort(arr, place);
    }
排序算法复杂度

折半插入排序 平均时间复杂度为O(n^2) 最坏时间复杂度为O(n^2)
最好时间复杂度为 O(nlog2(n)) 空间复杂度为 O(1)
稳定性为 稳定

记忆技巧：

    时间复杂度：“快些以nlog2(n)的速度归队”。“快” 指快速排序，“些” 指希尔排序，“归” 指归并排序，“队” 指堆排序（谐音）。这4种排序的平均复杂度都是O(nlog2(n))算法稳定性：“写代码太痛苦了，情绪不稳定，快些选一堆好友来聊天吧”。“快” 指快速排序，“些” 指希尔排序，“选”指简单选择排序，“堆” 指堆排序，这 4 种是不稳定的，其他的都是稳定的。
代码汇总

主方法main:

public class Main {    //起泡（冒泡）排序
    public static void main(String[] args) {
        //构建长度为12的数组
        int[] arr = new int[]{49,38,65,97,49,77,13,27,1,100,2,15};
        Sorts s = new Sorts();
        //s.BubbleSort(arr,12);  //起泡排序
        //s.InsertSort(arr,12);  //直接插入排序
        //s.SelectSort(arr,12);  //简单选择排序
        //s.QuickSort(arr,0,11);  //快速排序

//        int low = 0;          //二路归并排序
//        int high = 11;
//        s.mergeSort(arr, low, high);
        //s.BInsertSort(arr,12);
        //s.ShellSort(arr,12);

        
//        int[] arr1 = new int[]{-1, 49, 38, 65, 97, 49, 77, 13, 27, 1, 100, 2, 15};
//        s.heapSort(arr1, 12) ;
//        System.out.print("堆排序：");
//        for (int i :
//                arr1) {
//            System.out.print(i+"  ");
//        }
//        System.out.println();

        s.radixSort(arr);
        for (int i :
                arr) {
            System.out.print(i+"  ");
        }
    }

}

排序Sorts类：

public class Sorts {
    //起泡（冒泡）算法
    public void BubbleSort(int[] arr, int n){ //改进的冒泡排序
        int temp;
        int flag;
        for (int i = n-1; i >= 1 ; i--) {
            flag = 0; //变量flag用来标记本趟排序是否发生了交换
            for (int j = 1; j <= i; j++) {
                if (arr[j-1] > arr[j]){
                    flag = 1;  //如果发生了交换，flag置为1
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
            if (flag == 0) { //则证明序列有序，排序结束
                return;      //一趟排序过程中没有发生关键字交换
            }
        }
    }
//直接插入排序
    public void InsertSort(int[] arr, int n){
        int temp;
        int j;
        for (int i = 1; i < n; i++) {
            temp = arr[i]; //将待插入关键字暂存到temp中
            j = i-1;
            while (j >= 0 && temp < arr[j]){ //j>=0为了防止超出数组前部界限
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp; //找到插入位置，将temp中暂存的待排序关键字插入
        }
    }
//简单选择排序
    public void SelectSort(int[] arr,int n){
        int temp;
        int k;
        for (int i = 0; i < n; i++) {
            k = i;
            
            for (int j = i+1; j < n; j++) {
                if (arr[k] > arr[j]) {
                    k = j;
                }
            }
            if(k != i){
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }

        }
    }
//快速排序
    public void QuickSort(int[] arr, int low, int high){
        int temp;
        int i = low;
        int j = high;
        if (i < j){
            temp = arr[low];
            while (i < j){
                while (i < j && temp <= arr[j]) j--;
                if (i < j){
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && temp >= arr[i]) i++;
                if (i < j){
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = temp;
            QuickSort(arr,low,i-1);
            QuickSort(arr,j+1,high);
        }
    }
//归并排序
    public void merge(int[] arr, int low, int mid, int high){
        int n1 = mid-low+1;
        int n2 = high-mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[low+i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid+j+1];
        }
        int i = 0;int j = 0;
        int k = low;
        while (i < n1 && j < n2){
            if(L[i] <= R[j]){
                arr[k++] = L[i++];
            }
            else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1){
            arr[k++] = L[i++];
        }
        while (j < n2){
            arr[k++] = R[j++];
        }
    }
    public void mergeSort(int[] arr, int low, int high){
        if(low < high){
            int mid = (high+low)/2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }

    //折半插入排序
    public void BInsertSort(int[] arr,int n){
        int low, mid, high;
        int temp;
        for (int i = 1; i < n; i++) {
            low = 0;
            high = i-1;
            temp = arr[i];
            while(low <= high){
                mid = (low+high)/2;
                if (temp > arr[mid]) low = mid+1;
                else high = mid-1;
            }
            for (int j = i-1; j > high; j--) {
                arr[j+1] = arr[j];  //high+1到i-1的关键字向后移一位
            }
            arr[high+1] = temp; //待插入关键字插入到high后面一位
        }
    }

    //希尔排序
    public void ShellSort(int[] arr, int n){
        int temp;
        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                temp = arr[i];
//                两种循环（for和while）均可实现子序列的排序
//                int j;
//                for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) arr[j] = arr[j-gap];
                int j = i;
                while (j >= gap && arr[j-gap] > temp) {
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    //堆排序
    
    void Sift(int[] arr, int low, int high){
        int i = low, j = 2 * i;   //arr[j]是arr[i]的左孩子
        int temp = arr[i];
        while (j <= high) {
            if (j < high && arr[j] < arr[j + 1]) ++j;  //如果右孩子较大，则把j指向右孩子
            if (temp < arr[j]) {                      //j变成2*i+1
                arr[i] = arr[j];    //将arr[j]调整到双亲节点的位置上
                i = j;              //修改i和j的值，以便继续向下调整
                j = 2 * i;
            } else {
                break;
            }
        }
        arr[i] = temp;  //将调整节点的值放在最终位置
    }

    void heapSort(int[] arr, int n){
        int temp;
        for (int i = n / 2; i >= 1; --i)    //建立初始堆
            Sift(arr, i, n);
        for (int i = n; i >= 2; --i) {      //进行n-1次循环，完成堆排序
            temp = arr[1];
            arr[1] = arr[i];
            arr[i] = temp;
            Sift(arr, 1, i - 1);    //在减少了1个关键字的无序序列中进行调整
        }

    }

    //基数排序
    public void countingSort(int[] arr, int place) {
        int size = arr.length;
        int[] output = new int[size];
        // 假设第一个元素指定数位上的值最大
        int max = (arr[0] / place) % 10;
        // 找到真正数位上值最大的元素
        for (int i = 1; i < size; i++) {
            if (((arr[i] / place) % 10) > max)
                max = (arr[i] / place) % 10;
        }
        // 创建并初始化 count 数组
        int[] count = new int[10];
        for (int i = 0; i < 10; ++i)
            count[i] = 0;
        // 统计各个元素出现的次数
        for (int i = 0; i < size; i++)
            count[(arr[i] / place) % 10]++;
        // 累加 count 数组中的出现次数
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        // 根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
        for (int i = size - 1; i >= 0; i--) {
            output[count[(arr[i] / place) % 10] - 1] = arr[i];
            count[(arr[i] / place) % 10]--;
        }
        // 将 output 数组中的数据原封不动地拷贝到 arr 数组中
        for (int i = 0; i < size; i++)
            arr[i] = output[i];
    }
    // 找到整个序列中的最大值
    public int getMax(int[] arr) {
        int size = arr.length;
        int max = arr[0];
        for (int i = 1; i < size; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }

    public void radixSort(int[] arr) {
        // 找到序列中的最大值
        int max = getMax(arr);
        // 根据最大值具有的位数，从低位依次调用计数排序算法
        for (int place = 1; max / place > 0; place *= 10)
            countingSort(arr, place);
    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5712208.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
ccer ccer 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存