devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

JAVA数据处理（实现7种排序算法）_java各种排序算法实现

作者：我家自动化 | 2024-04-21 09:05:06

赞

踩

java各种排序算法实现

                        选择排序是一种简单的排序算法，其基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。

具体实现步骤如下：

  1. 设数组长度为n。
  2. 从第1个元素开始，依次与后面所有元素比较，找到最小值，并记录其下标。
  3. 将第1个元素和最小值元素进行交换。
  4. 从第2个元素开始，重复步骤2和3，直到排序完成。
  5. 代码示例： 
    1. public class SelectionSort {
    2.     public static void selectionSort(int[] arr) {
    3.         int n = arr.length;
    4.         for (int i = 0; i < n - 1; i++) {
    5.             int minIndex = i;
    6.             for (int j = i + 1; j < n; j++) {
    7.                 if (arr[j] < arr[minIndex]) {
    8.                     minIndex = j;
    9.                 }
    10.             }
    11.             int temp = arr[i];
    12.             arr[i] = arr[minIndex];
    13.             arr[minIndex] = temp;
    14.         }
    15.     }
    16.  
    17.     public static void main(String[] args) {
    18.         int[] arr = {64, 25, 12, 22, 11};
    19.         selectionSort(arr);
    20.         System.out.println("Sorted array:");
    21.         for (int num : arr) {
    22.             System.out.print(num + " ");
    23.         }
    24.     }
    25. }

  • 冒泡排序.

冒泡排序是一种简单的排序算法，其基本思想是通过相邻元素之间的比较和交换，依次将待排序的元素“浮”到正确的位置。

具体实现步骤如下：

  1. 从第一个元素开始，依次比较相邻的两个元素，如果它们的顺序不正确（比如前面的元素大于后面的元素），则交换它们的位置。
  2. 继续比较下一组相邻元素，直到整个序列按照升序或降序排列。
  3. 代码示例： 
    1. public class BubbleSort {
    2.     public static void bubbleSort(int[] arr) {
    3.         int n = arr.length;
    4.         for (int i = 0; i < n - 1; i++) {
    5.             for (int j = 0; j < n - i - 1; j++) {
    6.                 if (arr[j] > arr[j + 1]) {
    7.                     // 交换arr[j]和arr[j+1]
    8.                     int temp = arr[j];
    9.                     arr[j] = arr[j + 1];
    10.                     arr[j + 1] = temp;
    11.                 }
    12.             }
    13.         }
    14.     }
    15.  
    16.     public static void main(String[] args) {
    17.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
    18.         bubbleSort(arr);
    19.         System.out.println("Sorted array:");
    20.         for (int num : arr) {
    21.             System.out.print(num + " ");
    22.         }
    23.     }
    24. }

  • 堆排序.

堆排序是一种树形选择排序，它利用堆这种数据结构进行排序。堆是一个近似完全二叉树的结构，并同时满足堆的性质：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

堆排序的基本思想如下：

  1. 构建最大堆（大顶堆）或最小堆（小顶堆），将待排序序列构建成堆。
  2. 将堆顶元素（最大值或最小值）与堆的最后一个元素交换位置，使得堆的规模减一。
  3. 重新调整堆，使得剩余元素依然满足堆的性质。
  4. 重复步骤2和3，直到堆中只剩下一个元素，即完成排序。
  5. 代码示例： 
    1. public class HeapSort {
    2.     public void heapSort(int arr[]) {
    3.         int n = arr.length;
    4.  
    5.         // 构建最大堆
    6.         for (int i = n / 2 - 1; i >= 0; i--) {
    7.             heapify(arr, n, i);
    8.         }
    9.  
    10.         // 依次取出堆顶元素，调整堆
    11.         for (int i = n - 1; i > 0; i--) {
    12.             // 将堆顶元素与当前堆的最后一个元素交换
    13.             int temp = arr[0];
    14.             arr[0] = arr[i];
    15.             arr[i] = temp;
    16.  
    17.             // 调整堆，重新构建最大堆
    18.             heapify(arr, i, 0);
    19.         }
    20.     }
    21.  
    22.     void heapify(int arr[], int n, int i) {
    23.         int largest = i;
    24.         int l = 2 * i + 1;
    25.         int r = 2 * i + 2;
    26.  
    27.         if (l < n && arr[l] > arr[largest]) {
    28.             largest = l;
    29.         }
    30.  
    31.         if (r < n && arr[r] > arr[largest]) {
    32.             largest = r;
    33.         }
    34.  
    35.         if (largest != i) {
    36.             int swap = arr[i];
    37.             arr[i] = arr[largest];
    38.             arr[largest] = swap;
    39.  
    40.             heapify(arr, n, largest);
    41.         }
    42.     }
    43.  
    44.     public static void main(String args[]) {
    45.         int arr[] = {12, 11, 13, 5, 6, 7};
    46.         HeapSort ob = new HeapSort();
    47.         ob.heapSort(arr);
    48.         System.out.println("Sorted array is");
    49.         for (int i : arr) {
    50.             System.out.print(i + " ");
    51.         }
    52.     }
    53. }

  • 插入排序.

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对未排序的数据逐个插入到已排序的部分中，从而获得最终的排序结果。

具体实现步骤如下：

  1. 从第一个元素开始，该元素可以视为已排序部分。
  2. 取出未排序部分的第一个元素，在已排序部分中从后向前逐个比较，找到合适的位置插入该元素。
  3. 重复步骤2，直到所有元素都插入到已排序部分。
  4. 代码示例： 
    1. public class InsertionSort {
    2.     public void insertionSort(int arr[]) {
    3.         int n = arr.length;
    4.         for (int i = 1; i < n; i++) {
    5.             int key = arr[i];
    6.             int j = i - 1;
    7.             while (j >= 0 && arr[j] > key) {
    8.                 arr[j + 1] = arr[j];
    9.                 j = j - 1;
    10.             }
    11.             arr[j + 1] = key;
    12.         }
    13.     }
    14.  
    15.     public static void main(String args[]) {
    16.         int arr[] = {12, 11, 13, 5, 6};
    17.         InsertionSort ob = new InsertionSort();
    18.         ob.insertionSort(arr);
    19.         System.out.println("Sorted array is");
    20.         for (int i : arr) {
    21.             System.out.print(i + " ");
    22.         }
    23.     }
    24. }

  • 希尔排序.

希尔排序是一种改进的插入排序算法，也称为“缩小增量排序”。它通过将原始序列分割成若干子序列进行插入排序，从而使得整个序列基本有序，最后再对整个序列进行一次插入排序。

具体实现步骤如下：

  1. 选取一个增量序列（通常为希尔增量），按照增量序列对序列进行分组。
  2. 对每个组内的元素进行插入排序。
  3. 缩小增量，重复步骤1和2，直到增量为1。
  4. 代码示例： 
    1. public class ShellSort {
    2.     public void shellSort(int arr[]) {
    3.         int n = arr.length;
    4.  
    5.         // 选择希尔增量序列
    6.         int gap = 1;
    7.         while (gap < n / 3) {
    8.             gap = gap * 3 + 1;
    9.         }
    10.  
    11.         // 缩小增量，重复插入排序
    12.         while (gap > 0) {
    13.             for (int i = gap; i < n; i++) {
    14.                 int temp = arr[i];
    15.                 int j = i;
    16.                 while (j >= gap && arr[j - gap] > temp) {
    17.                     arr[j] = arr[j - gap];
    18.                     j -= gap;
    19.                 }
    20.                 arr[j] = temp;
    21.             }
    22.             gap = (gap - 1) / 3;
    23.         }
    24.     }
    25.  
    26.     public static void main(String args[]) {
    27.         int arr[] = {12, 11, 13, 5, 6, 7};
    28.         ShellSort ob = new ShellSort();
    29.         ob.shellSort(arr);
    30.         System.out.println("Sorted array is");
    31.         for (int i : arr) {
    32.             System.out.print(i + " ");
    33.         }
    34.     }
    35. }

希尔增量的选择可以影响算法性能，常用的希尔增量序列有Hibbard增量、Sedgewick增量等。

  • 归并排序.

归并排序是一种基于分治思想的排序算法，它将原始序列分割成较小的子序列，然后不断地合并两个有序子序列，直到整个序列有序为止。

具体实现步骤如下：

  1. 分解：将原始序列分解成较小的子序列，直到无法再分解（即子序列只包含一个元素）。
  2. 合并：将两个有序子序列合并成一个大的有序序列。
  3. 重复步骤2，直到所有子序列合并完毕，得到最终的有序序列。
  4. 代码示例： 
    1. public class MergeSort {
    2.     public void merge(int arr[], int l, int m, int r) {
    3.         int n1 = m - l + 1;
    4.         int n2 = r - m;
    5.  
    6.         int L[] = new int[n1];
    7.         int R[] = new int[n2];
    8.  
    9.         for (int i = 0; i < n1; ++i) {
    10.             L[i] = arr[l + i];
    11.         }
    12.         for (int j = 0; j < n2; ++j) {
    13.             R[j] = arr[m + 1 + j];
    14.         }
    15.  
    16.         int i = 0, j = 0;
    17.         int k = l;
    18.         while (i < n1 && j < n2) {
    19.             if (L[i] <= R[j]) {
    20.                 arr[k] = L[i];
    21.                 i++;
    22.             } else {
    23.                 arr[k] = R[j];
    24.                 j++;
    25.             }
    26.             k++;
    27.         }
    28.  
    29.         while (i < n1) {
    30.             arr[k] = L[i];
    31.             i++;
    32.             k++;
    33.         }
    34.  
    35.         while (j < n2) {
    36.             arr[k] = R[j];
    37.             j++;
    38.             k++;
    39.         }
    40.     }
    41.  
    42.     public void mergeSort(int arr[], int l, int r) {
    43.         if (l < r) {
    44.             int m = (l + r) / 2;
    45.             mergeSort(arr, l, m);
    46.             mergeSort(arr, m + 1, r);
    47.             merge(arr, l, m, r);
    48.         }
    49.     }
    50.  
    51.     public static void main(String args[]) {
    52.         int arr[] = {12, 11, 13, 5, 6, 7};
    53.         MergeSort ob = new MergeSort();
    54.         ob.mergeSort(arr, 0, arr.length - 1);
    55.         System.out.println("Sorted array is");
    56.         for (int i : arr) {
    57.             System.out.print(i + " ");
    58.         }
    59.     }
    60. }

  • 快速排序.

快速排序是一种常用的基于分治思想的排序算法，由C. A. R. Hoare在1960年提出。

快速排序的实现步骤如下：

  1. 选择一个基准元素（通常为序列的第一个元素），将序列分成两个子序列，其中一个子序列的所有元素都小于基准元素，另一个子序列的所有元素都大于基准元素。
  2. 对子序列递归重复步骤1，直到子序列中只包含一个元素，此时整个序列有序。
  3. 代码示例： 
    1. public class QuickSort {
    2.     public int partition(int arr[], int low, int high) {
    3.         int pivot = arr[high];
    4.         int i = (low - 1);
    5.         for (int j = low; j < high; j++) {
    6.             if (arr[j] <= pivot) {
    7.                 i++;
    8.  
    9.                 int temp = arr[i];
    10.                 arr[i] = arr[j];
    11.                 arr[j] = temp;
    12.             }
    13.         }
    14.  
    15.         int temp = arr[i + 1];
    16.         arr[i + 1] = arr[high];
    17.         arr[high] = temp;
    18.  
    19.         return i + 1;
    20.     }
    21.  
    22.     public void quickSort(int arr[], int low, int high) {
    23.         if (low < high) {
    24.             int pi = partition(arr, low, high);
    25.  
    26.             quickSort(arr, low, pi - 1);
    27.             quickSort(arr, pi + 1, high);
    28.         }
    29.     }
    30.  
    31.     public static void main(String args[]) {
    32.         int arr[] = {12, 11, 13, 5, 6, 7};
    33.         QuickSort ob = new QuickSort();
    34.         ob.quickSort(arr, 0, arr.length - 1);
    35.         System.out.println("Sorted array is");
    36.         for (int i : arr) {
    37.             System.out.print(i + " ");
    38.         }
    39.     }
    40. }

    快速排序的时间复杂度为O(nlogn)，并且通常具有更好的性能表现，适合各种数据规模的排序。它也是许多其他排序算法的基础，例如堆排序和归并排序。

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

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

  

闽ICP备14008679号