八大排序算法代码

谁借莪１个温暖的怀抱￠ 2021-11-16 23:01 257阅读 0赞

### 一、冒泡排序算法： ###

1、一般写法：

int temp;
            //外层循环是排序的趟数
            for (int i = 0; i < arrays.length - 1 ; i++) {
                //内层循环是当前趟数需要比较的次数
                for (int j = 0; j < arrays.length - i - 1; j++) {
                    //前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
                    if (arrays[j] > arrays[j + 1]) {
                        temp = arrays[j];
                        arrays[j] = arrays[j + 1];
                        arrays[j + 1] = temp;
                    }
                }
            }

2、优化写法：

//装载临时变量
            int temp;
            //记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
            int isChange;
            //外层循环是排序的趟数
            for (int i = 0; i < arrays.length - 1; i++) {
                //每比较一趟就重新初始化为0
                isChange = 0;
                //内层循环是当前趟数需要比较的次数
                for (int j = 0; j < arrays.length - i - 1; j++) {
                    //前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
                    if (arrays[j] > arrays[j + 1]) {
                        temp = arrays[j];
                        arrays[j] = arrays[j + 1];
                        arrays[j + 1] = temp;
                        //如果进到这里面了，说明发生置换了
                        isChange = 1;
                    }
                }
                //如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
                if (isChange == 0) {
                    break;
                }
            }

### 二、选择排序算法： ###

//记录当前趟数的最大值的角标
        int pos ;
        //交换的变量
        int temp;
        //外层循环控制需要排序的趟数
        for (int i = 0; i < arrays.length - 1; i++) {
            //新的趟数、将角标重新赋值为0
            pos = 0;
            //内层循环控制遍历数组的个数并得到最大数的角标
            for (int j = 0; j < arrays.length - i; j++) {          
                if (arrays[j] > arrays[pos]) {
                    pos = j;
                }
            }
            //交换
            temp = arrays[pos];
            arrays[pos] = arrays[arrays.length - 1 - i];
            arrays[arrays.length - 1 - i] = temp;
        }
        System.out.println(arrays);

### 三、快速排序算法 ###

public static void main(String[] args) {
            int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};
            quickSort(arr, 0, 9);
            System.out.println("Java3y   " + arr);
        }
    
        /**
         * 快速排序
         *
         * @param arr
         * @param L   指向数组第一个元素
         * @param R   指向数组最后一个元素
         */
        public static void quickSort(int[] arr, int L, int R) {
            int i = L;
            int j = R;
            //支点
            int pivot = arr[(L + R) / 2];
            //左右两端进行扫描，只要两端还没有交替，就一直扫描
            while (i <= j) {
                //寻找直到比支点大的数
                while (pivot > arr[i])
                    i++;
                //寻找直到比支点小的数
                while (pivot < arr[j])
                    j--;
                //此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
                if (i <= j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }
            //上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
            //“左边”再做排序，直到左边剩下一个数(递归出口)
            if (L < j)
                quickSort(arr, L, j);
            //“右边”再做排序，直到右边剩下一个数(递归出口)
            if (i < R)
                quickSort(arr, i, R);
        }

### 四、插入排序算法 ###

public static void sort(int[] arrays) {       
            //临时变量
            int temp;
            //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
            for (int i = 1; i < arrays.length; i++) {
                temp = arrays[i];
                //如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
                int j = i - 1;
                while (j >= 0 && arrays[j] > temp) {
                    //往后退一个位置，让当前数据与之前前位进行比较
                    arrays[j + 1] = arrays[j];
                    //不断往前，直到退出循环
                    j--;
                }
                //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
                arrays[j + 1] = temp;
            }
            System.out.println(arrays);
        }

### 五、希尔排序算法 ###

public static void shellSort(int[] arrays) {
            //增量每次都/2
            for (int step = arrays.length / 2; step > 0; step /= 2) {
                //从增量那组开始进行插入排序，直至完毕
                for (int i = step; i < arrays.length; i++) {
                    int j = i;
                    int temp = arrays[j];
                    // j - step 就是代表与它同组隔壁的元素
                    while (j - step >= 0 && arrays[j - step] > temp) {
                        arrays[j] = arrays[j - step];
                        j = j - step;
                    }
                    arrays[j] = temp;
                }
            }
        }

### 六、归并排序算法 ###

public static void main(String[] args) {
            int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
            mergeSort(arrays, 0, arrays.length - 1);
            System.out.println(arrays);
        }
    
        /**
         * 归并排序
         *
         * @param arrays
         * @param L      指向数组第一个元素
         * @param R      指向数组最后一个元素
         */
        public static void mergeSort(int[] arrays, int L, int R) {
            //如果只有一个元素，那就不用排序了
            if (L == R) {
                return;
            } else {
                //取中间的数，进行拆分
                int M = (L + R) / 2;
                //左边的数不断进行拆分
                mergeSort(arrays, L, M);
                //右边的数不断进行拆分
                mergeSort(arrays, M + 1, R);
                //合并
                merge(arrays, L, M + 1, R);
            }
        }
    
    
        /**
         * 合并数组
         *
         * @param arrays
         * @param L      指向数组第一个元素
         * @param M      指向数组分隔的元素
         * @param R      指向数组最后的元素
         */
        public static void merge(int[] arrays, int L, int M, int R) {
            //左边的数组的大小
            int[] leftArray = new int[M - L];
            //右边的数组大小
            int[] rightArray = new int[R - M + 1];
            //往这两个数组填充数据
            for (int i = L; i < M; i++) {
                leftArray[i - L] = arrays[i];
            }
            for (int i = M; i <= R; i++) {
                rightArray[i - M] = arrays[i];
            }
    
            int i = 0, j = 0;
            // arrays数组的第一个元素
            int  k = L;
    
            //比较这两个数组的值，哪个小，就往数组上放
            while (i < leftArray.length && j < rightArray.length) {
                //谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个
                // 等于的情况是保证“稳定”
                if (leftArray[i] <= rightArray[j]) {
                    arrays[k] = leftArray[i];
                    i++;
                    k++;
                } else {
                    arrays[k] = rightArray[j];
                    j++;
                    k++;
                }
            }
            //如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)
            while (i < leftArray.length) {
                arrays[k] = leftArray[i];
    
                i++;
                k++;
            }
            //如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)
            while (j < rightArray.length) {
                arrays[k] = rightArray[j];
    
                k++;
                j++;
            }
        }

### 七、基数排序算法 ###

public static void radixSort(int[] arrays) {
            int max = findMax(arrays, 0, arrays.length - 1);
            //需要遍历的次数由数组最大值的位数来决定
            for (int i = 1; max / i > 0; i = i * 10) {
                int[][] buckets = new int[arrays.length][10];
                //获取每一位数字(个、十、百、千位...分配到桶子里)
                for (int j = 0; j < arrays.length; j++) {
                    int num = (arrays[j] / i) % 10;
                    //将其放入桶子里
                    buckets[j][num] = arrays[j];
                }
                //回收桶子里的元素
                int k = 0;
                //有10个桶子
                for (int j = 0; j < 10; j++) {
                    //对每个桶子里的元素进行回收
                    for (int l = 0; l < arrays.length ; l++) {
                        //如果桶子里面有元素就回收(数据初始化会为0)
                        if (buckets[l][j] != 0) {
                            arrays[k++] = buckets[l][j];
                        }                  
                    }                
                }
            }
        }

/**
         * 递归，找出数组最大的值
         * @param arrays 数组
         * @param L      左边界，第一个数
         * @param R      右边界，数组的长度
         * @return
         */
    
        public static int findMax(int[] arrays, int L, int R) {
            //如果该数组只有一个数，那么最大的就是该数组第一个值了
            if (L == R) {
                return arrays[L];
            } else {
                int a = arrays[L];
                int b = findMax(arrays, L + 1, R);//找出整体的最大值
                if (a > b) {
                    return a;
                } else {
                    return b;
                }
            }

### 八、堆排序算法 ###

/**
         * 建堆
         *
         * @param arrays          看作是完全二叉树
         * @param currentRootNode 当前父节点位置
         * @param size            节点总数
         */
        public static void heapify(int[] arrays, int currentRootNode, int size) {
            if (currentRootNode < size) {
                //左子树和右字数的位置
                int left = 2 * currentRootNode + 1;
                int right = 2 * currentRootNode + 2;
                //把当前父节点位置看成是最大的
                int max = currentRootNode;
                if (left < size) {
                    //如果比当前根元素要大，记录它的位置
                    if (arrays[max] < arrays[left]) {
                        max = left;
                    }
                }
                if (right < size) {
                    //如果比当前根元素要大，记录它的位置
                    if (arrays[max] < arrays[right]) {
                        max = right;
                    }
                }
                //如果最大的不是根元素位置，那么就交换
                if (max != currentRootNode) {
                    int temp = arrays[max];
                    arrays[max] = arrays[currentRootNode];
                    arrays[currentRootNode] = temp;
    
                    //继续比较，直到完成一次建堆
                    heapify(arrays, max, size);
                }
            }
        }

/**
         * 完成一次建堆，最大值在堆的顶部(根节点)
         */
        public static void maxHeapify(int[] arrays, int size) {
            // 从数组的尾部开始，直到第一个元素(角标为0)
            for (int i = size - 1; i >= 0; i--) {
                heapify(arrays, i, size);
            }
        }

for (int i = 0; i < arrays.length; i++) {
    
            //每次建堆就可以排除一个元素了
            maxHeapify(arrays, arrays.length - i);
    
            //交换
            int temp = arrays[0];
            arrays[0] = arrays[(arrays.length - 1) - i];
            arrays[(arrays.length - 1) - i] = temp;
    
        }

算法详细解释见：[https://github.com/ZhongFuCheng3y/3y/blob/master/src/sort.md][https_github.com_ZhongFuCheng3y_3y_blob_master_src_sort.md]

[https_github.com_ZhongFuCheng3y_3y_blob_master_src_sort.md]: https://github.com/ZhongFuCheng3y/3y/blob/master/src/sort.md