devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法——排序算法

作者：菜鸟追梦旅行 | 2024-02-25 05:01:55

赞

踩

算法——排序算法

目录

1、冒泡排序

2、插入排序

3、选择排序

4、归并排序

5、快速排序

 6、堆排序

 7、计数排序

 8、桶排序

 9、基数排序

常见的排序算法包括：

  1. 冒泡排序（Bubble Sort）
  2. 插入排序（Insertion Sort）
  3. 选择排序（Selection Sort）
  4. 归并排序（Merge Sort）
  5. 快速排序（Quick Sort）
  6. 堆排序（Heap Sort）
  7. 计数排序（Counting Sort）
  8. 桶排序（Bucket Sort）
  9. 基数排序（Radix Sort）

1、冒泡排序

  • 工作原理：
    • 1、比较相邻的两个元素。如果前面的元素大于后面的元素，则交换它们的位置；
    • 2、对每一对相邻的元素进行同样的操作，从开始第一对到结尾的最后一对，这样一趟比较结束后，最大的元素就"沉"到了数列的最末尾；
    • 3、针对所有的元素重复以上的步骤，除了最后一个；
    • 4、重复步骤1~3，当没有相邻的元素需要交换时，排序就完成了。

冒泡排序示例代码：

  1. public class BubbleSort {
  2.     public static void main(String[] args) {
  3.         int[] arr = {5, 2, 9, 1, 5, 6};
  4.         bubbleSort(arr);
  5.         System.out.println("\n排序后的数组：");
  6.         for (int num : arr) {
  7.             System.out.print(num + " ");
  8.         }
  9.     }
  10.     
  11.     public static void bubbleSort(int[] arr) {
  12.         int n = arr.length;
  13.         boolean swapped;
  14.         
  15.         for (int i = 0; i < n - 1; i++) {
  16.             swapped = false;
  17.             for (int j = 0; j < n - i - 1; j++) {
  18.                 if (arr[j] > arr[j + 1]) {
  19.                     // 交换 arr[j] 和 arr[j + 1]
  20.                     int temp = arr[j];
  21.                     arr[j] = arr[j + 1];
  22.                     arr[j + 1] = temp;
  23.                     swapped = true;
  24.                 }
  25.             }
  26.             // 如果没有发生交换，说明数组已经有序
  27.             if (!swapped) {
  28.                 break;
  29.             }
  30.         }
  31.     }
  32. }

2、插入排序

  • 工作原理：
    • 从第一个元素开始，该元素可以认为已经被排序。
    • 取出下一个元素，在已经排序的元素序列中从后向前扫描。
    • 如果该元素（已排序）大于新元素，将该元素移到下一位置。
    • 重复步骤 3，直到找到已排序的元素小于或等于新元素的位置。
    • 将新元素插入到该位置后。
    • 重复步骤 2~5，数组经过 n-1 次遍历后就会变成有序序列。

插入排序示例代码：

  1. public class InsertionSort {
  2.     // 插入排序算法实现
  3.     public static void insertionSort(int[] array) {
  4.         int n = array.length;
  5.         // 从第二个元素开始遍历数组
  6.         for (int i = 1; i < n; i++) {
  7.             int key = array[i]; // 当前要插入的值
  8.             int j = i - 1; // 已排序部分的最后一个元素的下标
  9.             // 在已排序部分中寻找合适的位置插入key
  10.             while (j >= 0 && array[j] > key) {
  11.                 array[j + 1] = array[j]; // 向后移动元素
  12.                 j--;
  13.             }
  14.             array[j + 1] = key; // 将key插入合适的位置
  15.         }
  16.     }
  17.  
  18.     public static void main(String[] args) {
  19.         int[] arr = {12, 11, 13, 5, 6};
  20.         insertionSort(arr);
  21.         System.out.print("Sorted array: ");
  22.         for (int i : arr) {
  23.             System.out.print(i + " ");
  24.         }
  25.     }
  26. }

3、选择排序

  • 工作原理：
    • 1、首先，从未排序的元素中找到最小（或最大）的元素。
    • 2、将其放到已排序序列的末尾（或者放到另一个数组的开头）。
    • 3、然后，再从剩余的未排序元素中找到最小（或最大）的元素，放到已排序序列的末尾。
    • 4、重复步骤 2 和步骤 3，直到所有元素都已排序。

 选择排序的伪代码：

  1. function selectionSort(array)
  2.     n = array.length
  3.     for i from 0 to n-1
  4.         minIndex = i
  5.         for j from i+1 to n-1
  6.             if array[j] < array[minIndex]
  7.                 minIndex = j
  8.         swap array[i] and array[minIndex]
  9.     end for
  10. end function
  11. //外层循环遍历数组，
  12. //内层循环找到未排序部分中的最小元素，并将其与当前外层循环位置的元素交换，
  13. //这样就不断地将最小元素放到已排序部分的末尾，直到整个数组都排序完成

4、归并排序

  • 工作原理：

    • 分解：将待排序的数组不断地二分，直到每个子序列只有一个元素为止。

    • 排序：对每个子序列进行排序，可以采用递归的方式来实现。

    • 合并：将排好序的子序列再合并为一个整体有序的数组。

归并排序示例代码：

  1. public class MergeSort {
  2.  
  3.     // 归并排序的主函数，对数组array进行归并排序
  4.     public static void mergeSort(int[] array, int left, int right) {
  5.         if (left < right) {
  6.             // 计算中间位置
  7.             int middle = (left + right) / 2;
  8.             // 递归地对左半部分进行归并排序
  9.             mergeSort(array, left, middle);
  10.             // 递归地对右半部分进行归并排序
  11.             mergeSort(array, middle + 1, right);
  12.             // 合并左右两部分
  13.             merge(array, left, middle, right);
  14.         }
  15.     }
  16.  
  17.     // 将两个已经排序的数组段 array[left...middle] 和 array[middle+1...right] 合并成一个有序数组
  18.     public static void merge(int[] array, int left, int middle, int right) {
  19.         // 计算左右两部分数组段的长度
  20.         int n1 = middle - left + 1;
  21.         int n2 = right - middle;
  22.  
  23.         // 创建临时数组存储左右两部分的数据
  24.         int[] leftArray = new int[n1];
  25.         int[] rightArray = new int[n2];
  26.  
  27.         // 将数据拷贝到临时数组
  28.         for (int i = 0; i < n1; i++) {
  29.             leftArray[i] = array[left + i];
  30.         }
  31.         for (int i = 0; i < n2; i++) {
  32.             rightArray[i] = array[middle + i + 1];
  33.         }
  34.  
  35.         // 合并左右两部分数组段
  36.         int i = 0, j = 0;
  37.         int k = left;
  38.         while (i < n1 && j < n2) {
  39.             if (leftArray[i] <= rightArray[j]) {
  40.                 array[k] = leftArray[i];
  41.                 i++;
  42.             } else {
  43.                 array[k] = rightArray[j];
  44.                 j++;
  45.             }
  46.             k++;
  47.         }
  48.  
  49.         // 将剩余的元素拷贝到数组中
  50.         while (i < n1) {
  51.             array[k] = leftArray[i];
  52.             i++;
  53.             k++;
  54.         }
  55.  
  56.         while (j < n2) {
  57.             array[k] = rightArray[j];
  58.             j++;
  59.             k++;
  60.         }
  61.     }
  62. }

5、快速排序

工作原理：

  • 选取一个基准元素（通常选择第一个元素），将序列分割为两个子序列；
  • 将小于基准的元素放在基准的左边，大于基准的元素放在右边；
  • 对左右子序列分别进行递归快速排序；
  • 合并左右子序列。

快速排序的示例代码：

  1. public class QuickSort {
  2.     public static void main(String[] args) {
  3.         int[] arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};
  4.         quickSort(arr, 0, arr.length - 1); // 调用快速排序算法
  5.         for (int i : arr) {
  6.             System.out.print(i + " "); // 输出排序后的数组
  7.         }
  8.     }
  9.  
  10.     public static void quickSort(int[] arr, int low, int high) {
  11.         if (arr == null || arr.length == 0 || low >= high) {
  12.             return; // 如果数组为空或者low大于等于high，直接返回
  13.         }
  14.         int middle = low + (high - low) / 2; // 计算中间值的索引
  15.         int pivot = arr[middle]; // 取得中间值作为基准值
  16.         int i = low, j = high; // 初始化i和j作为左右指针
  17.         while (i <= j) { // 当i小于等于j时循环
  18.             while (arr[i] < pivot) { // 在左半部分找到第一个大于等于基准值的元素
  19.                 i++;
  20.             }
  21.             while (arr[j] > pivot) { // 在右半部分找到第一个小于等于基准值的元素
  22.                 j--;
  23.             }
  24.             if (i <= j) { // 如果左指针小于等于右指针
  25.                 int temp = arr[i]; // 交换arr[i]和arr[j]
  26.                 arr[i] = arr[j];
  27.                 arr[j] = temp;
  28.                 i++;
  29.                 j--;
  30.             }
  31.         }
  32.         if (low < j) { // 递归处理左半部分
  33.             quickSort(arr, low, j);
  34.         }
  35.         if (high > i) { // 递归处理右半部分
  36.             quickSort(arr, i, high);
  37.         }
  38.     }
  39. }

 6、堆排序

工作原理：

  • 构建堆：首先将待排序的数据构建成一个二叉堆，可以是最大堆或最小堆。这个步骤可以使用从下往上的循环方式，从最后一个非叶子节点开始，逐个向前调整节点使得以当前节点为根的子树满足堆的性质。

  • 排序：将堆顶元素（最大值或最小值）与堆的最后一个元素交换位置，并将堆的大小减一。接着调整交换后的堆，使其满足堆的性质。重复以上步骤，直到整个数组排序完成。

堆排序的示例代码：

  1. 统计每个元素出现的次数：遍历待排序的数组，统计每个元素出现的次数，可以使用额外的辅助数组来保存计数结果。
  2. 根据元素的计数信息，确定元素在排序后的位置：根据元素值和它在计数数组中的计数位置，确定元素在排序后的位置。
  3. 将元素放置到正确的位置上：遍历待排序的数组，根据元素值在计数数组中的位置，将元素放置到正确的位置上。
  4. 输出排序后的结果：将排序后的元素依次输出，即得到排好序的数组。
  1. public class HeapSort {
  2.     // 堆排序的主要入口方法，用于对整个数组进行排序
  3.     public static void sort(int[] arr) {
  4.         // 构建最大堆
  5.         buildMaxHeap(arr);
  6.         
  7.         // 从最后一个非叶子节点开始，依次将根节点与末尾元素交换，并重新调整堆
  8.         for (int i = arr.length - 1; i > 0; i--) {
  9.             swap(arr, 0, i); // 将根节点与末尾元素交换
  10.             adjustHeap(arr, 0, i); // 重新调整堆
  11.         }
  12.     }
  13.  
  14.     // 构建最大堆的方法
  15.     private static void buildMaxHeap(int[] arr) {
  16.         int lastIndex = arr.length - 1;
  17.         int parentIndex = (lastIndex - 1) / 2; // 最后一个非叶子节点的下标
  18.         for (int i = parentIndex; i >= 0; i--) {
  19.             adjustHeap(arr, i, arr.length);
  20.         }
  21.     }
  22.  
  23.     // 调整堆的方法，使其满足最大堆的性质
  24.     private static void adjustHeap(int[] arr, int index, int length) {
  25.         int temp = arr[index]; // 当前父节点
  26.         for (int k = 2 * index + 1; k < length; k = 2 * k + 1) { // 从index结点的左子结点开始，也就是2*index+1处开始
  27.             if (k + 1 < length && arr[k] < arr[k + 1]) { // 如果左子结点小于右子结点，k指向右子结点
  28.                 k++;
  29.             }
  30.             if (arr[k] > temp) { // 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
  31.                 arr[index] = arr[k];
  32.                 index = k;
  33.             } else {
  34.                 break;
  35.             }
  36.         }
  37.         arr[index] = temp; // 将temp值放到最终的位置
  38.     }
  39.  
  40.     // 交换数组中两个元素的方法
  41.     private static void swap(int[] arr, int i, int j) {
  42.         int temp = arr[i];
  43.         arr[i] = arr[j];
  44.         arr[j] = temp;
  45.     }
  46.  
  47.     // 测试方法
  48.     public static void main(String[] args) {
  49.         int[] arr = {4, 6, 8, 5, 9, 1, 2, 3, 7};
  50.         sort(arr);
  51.         for (int num : arr) {
  52.             System.out.print(num + " ");
  53.         }
  54.     }
  55. }

 7、计数排序

工作原理：

  • 统计每个元素出现的次数：遍历待排序的数组，统计每个元素出现的次数，可以使用额外的辅助数组来保存计数结果。
  • 根据元素的计数信息，确定元素在排序后的位置：根据元素值和它在计数数组中的计数位置，确定元素在排序后的位置。
  • 将元素放置到正确的位置上：遍历待排序的数组，根据元素值在计数数组中的位置，将元素放置到正确的位置上。
  • 输出排序后的结果：将排序后的元素依次输出，即得到排好序的数组。

计数排序的示例代码：

  1. public class CountingSortExample {
  2.     public static void countingSort(int[] array, int max) {
  3.         int[] count = new int[max + 1]; // 创建计数数组，并初始化为 0
  4.  
  5.         for (int num : array) {
  6.             count[num]++; // 统计每个元素的个数
  7.         }
  8.  
  9.         int k = 0;
  10.         for (int i = 0; i < count.length; i++) {
  11.             while (count[i] > 0) {
  12.                 array[k] = i;  // 将计数数组中的元素按顺序填充到原始数组中
  13.                 k++;
  14.                 count[i]--;
  15.             }
  16.         }
  17.     }
  18.  
  19.     public static void main(String[] args) {
  20.         int[] array = {4, 2, 2, 8, 3, 3, 1};
  21.         int max = 8; // 数组中的最大值
  22.  
  23.         System.out.println("Before sorting: " + Arrays.toString(array));
  24.         countingSort(array, max);
  25.         System.out.println("After sorting: " + Arrays.toString(array));
  26.     }
  27. }

 8、桶排序

工作原理：

  • 遍历待排序数组，根据预设的规则将元素分配到对应的桶中。
  • 对每个桶内的元素进行排序，可以选择使用插入排序、快速排序等方法。
  • 将各个桶中的元素按顺序合并起来，得到最终的有序数组。
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3.  
  4. public class BucketSort {
  5.     public static void bucketSort(int[] nums) {
  6.         int bucketSize = 5; // 设置桶的大小
  7.         int maxValue = Integer.MIN_VALUE;
  8.         int minValue = Integer.MAX_VALUE;
  9.         for (int num : nums) {
  10.             maxValue = Math.max(maxValue, num); // 找到待排序数组的最大值
  11.             minValue = Math.min(minValue, num); // 找到待排序数组的最小值
  12.         }
  13.  
  14.         int bucketCount = (maxValue - minValue) / bucketSize + 1; // 计算桶的个数
  15.  
  16.         ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
  17.         for (int i = 0; i < bucketCount; i++) {
  18.             buckets.add(new ArrayList<>()); // 初始化桶
  19.         }
  20.  
  21.         for (int num : nums) {
  22.             int bucketIndex = (num - minValue) / bucketSize; // 计算元素应该放入的桶的索引
  23.             buckets.get(bucketIndex).add(num); // 将元素放入对应的桶中
  24.         }
  25.  
  26.         int index = 0;
  27.         for (ArrayList<Integer> bucket : buckets) {
  28.             Collections.sort(bucket); // 对每个桶内的元素进行排序
  29.             for (int num : bucket) {
  30.                 nums[index++] = num; // 将排序好的元素放回原数组
  31.             }
  32.         }
  33.     }
  34.  
  35.     public static void main(String[] args) {
  36.         int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
  37.         bucketSort(arr);
  38.         for (int num : arr) {
  39.             System.out.print(num + " ");
  40.         }
  41.     }
  42. }

 9、基数排序

工作原理：

  • 首先，将待排序的整数按照个位数的数值进行分配到 "桶" 中。
  • 然后，按照个位数的顺序将桶中的数字依次取出，组成一个新的序列。
  • 接着，再以十位数的数值进行分配到对应的桶中，并按顺序取出，形成新的序列。
  • 最后，以此类推，直到所有位数都分配完毕，得到有序的序列。

基数排序的示例代码：

  1. import java.util.ArrayList;
  2.  
  3. public class RadixSort {
  4.     // 获取数字的指定位数的数字
  5.     public static int getDigit(int number, int digitPlace) {
  6.         return (number / digitPlace) % 10;
  7.     }
  8.  
  9.     // 基数排序函数
  10.     public static void radixSort(int[] arr) {
  11.         // 找出数组中的最大值，以确定需要多少位数
  12.         int max = arr[0];
  13.         for (int num : arr) {
  14.             if (num > max) {
  15.                 max = num;
  16.             }
  17.         }
  18.  
  19.         // 计算最大值的位数
  20.         int numDigits = 1;
  21.         while (max > 9) {
  22.             max /= 10;
  23.             numDigits++;
  24.         }
  25.  
  26.         // 创建 10 个桶
  27.         ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
  28.         for (int i = 0; i < 10; i++) {
  29.             buckets.add(new ArrayList<>());
  30.         }
  31.  
  32.         // 进行排序
  33.         for (int digit = 1; digit <= Math.pow(10, numDigits - 1); digit *= 10) {
  34.             // 将数字分配到对应的桶中
  35.             for (int num : arr) {
  36.                 int digitVal = getDigit(num, digit);
  37.                 buckets.get(digitVal).add(num);
  38.             }
  39.  
  40.             // 从桶中取出数字，并按顺序放回原数组
  41.             int index = 0;
  42.             for (int i = 0; i < 10; i++) {
  43.                 for (int num : buckets.get(i)) {
  44.                     arr[index++] = num;
  45.                 }
  46.                 buckets.get(i).clear(); // 清空桶，以便下一轮排序使用
  47.             }
  48.         }
  49.     }
  50.  
  51.     // 测试
  52.     public static void main(String[] args) {
  53.         int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
  54.         radixSort(arr);
  55.  
  56.         System.out.print("排序后的数组：");
  57.         for (int num : arr) {
  58.             System.out.print(num + " ");
  59.         }
  60.     }
  61. }

一、1023: [编程入门]选择排序

题目描述
用选择法对10个整数从小到大排序。
输入格式
输入10个无序的数字
输出格式
排序好的10个整数
样例输入
4 85 3 234 45 345 345 122 30 12
样例输出
3
4
12
30
45
85
122
234
345
345

  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         Scanner scanner = new Scanner(System.in);
  5.         int[] array=new int[10];
  6.         for(int i=0;i<10;i++) {
  7.         	array[i]=scanner.nextInt();
  8.         }
  9.         selectionSort(array);
  10.     }
  11.     public static void selectionSort(int[] array) {
  12.     	for(int i=0;i<array.length;i++) {
  13.     		int minIndex=i;
  14.     		for(int j=i+1;j<array.length;j++) {//从未排序的元素中找到最小的元素
  15.     			if(array[j]<array[minIndex]) {
  16.     				minIndex=j;//更新最小元素的下标
  17.     			}
  18.     		}
  19.     		//将其放到已排序序列的末尾(0到i为已排序，j到n-1为未排序)
  20. 			int temp=array[i];
  21. 			array[i]=array[minIndex];
  22. 			array[minIndex]=temp;
  23.     	}
  24.     	for(int i=0;i<10;i++) {
  25.         	System.out.println(array[i]);
  26.         }
  27.     }
  28. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/138834?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号