Java深入了解数据结构中常见的排序算法

介绍

排序算法是计算机科学中最重要的基础问题之一。在本文中，我们将会介绍数据结构中常见的排序算法。排序算法在很多场景下都有应用，比如搜索、数据压缩、数据库等领域。

本文将会涉及以下排序算法：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序

我们将会通过示例代码来演示每一种算法的原理和实现。

冒泡排序

冒泡排序是最简单的排序算法之一。它的基本思想是通过比较相邻元素的大小，将较大的元素交换到右侧，从而实现整个数组的排序。

以下是Java实现冒泡排序的示例代码：

public class BubbleSort {
   public static void main(String []args) {
      int array[] = {5,90,35,45,150,3};
      int n = array.length;

      for (int i = 0; i < n-1; i++) {
         for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
               int temp = array[j];
               array[j] = array[j+1];
               array[j+1] = temp;
            }
         }
      }

      for (int i=0; i<n; ++i) {
         System.out.print(array[i] + " ");
      }
   }
}

上述代码首先定义了一个包含六个整型元素的数组。然后，执行了双重循环，一遍遍历数组，一遍比较相邻两个元素的大小，如果前面的元素大于后面的，就交换它们的位置。最后，对数组进行了输出。

选择排序

选择排序是一种最简单的排序算法之一。它的基本思想是：在未排序的数据中找到最小或最大的元素，与排序序列中的第一个元素交换位置，第一次找到最小元素后，就修订排序序列的起点。

以下是Java实现选择排序的示例代码：

 public class SelectionSort {

     public static void main(String[] args) {
         int[] arr = {8,5,1,6,3,2,7,4};
         int n = arr.length;

         for(int i=0;i<n-1;i++) {
             int min = i;
             for(int j=i+1;j<n;j++) {
                 if(arr[j]<arr[min]) {
                     min = j;
                 }
             }
             int temp = arr[min];
             arr[min] = arr[i];
             arr[i] = temp;
         }

         for (int i=0; i<n; ++i) {
             System.out.print(arr[i] + " ");
         }
     }
 }

上面的代码首先定义了一个包含八个整型元素的数组。然后，执行了双重循环，一遍遍历数组，一遍找到未排序部分的最小值，并与排序序列的起点进行交换，最后再输出数组。

插入排序

插入排序是一种最简单的排序算法之一。它的基本思想是，将一个未排序的数据序列，插入已经排序好的数据序列中。

以下是Java实现插入排序的示例代码：

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {8,5,1,6,3,2,7,4};
        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 = j - 1;
            }
            arr[j + 1] = key;
        }

        for (int i=0; i<n; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
}

上述代码首先定义了一个包含八个整型元素的数组。然后，执行了循环，一边遍历数组，一边将未排序部分的元素插入到排序序列中恰当的位置，最终再将数组输出。

快速排序

快速排序是一种高效的排序算法之一。它的基本思想是，将一个序列分成两个子序列，一边递归地排序子序列，最终将它们合并起来。

以下是Java实现快速排序的示例代码：

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {8, 5, 1, 6, 3, 2, 7, 4};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(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;
    }
}

上述代码首先定义了一个包含八个整型元素的数组。然后，执行了递归函数，将序列一分为二，分别排序后再合并，最终将数组输出。

归并排序

归并排序是一种高效的排序算法之一。它的基本思想是，将一个序列分成两个子序列，一边递归地排序子序列，最终将它们合并起来。

以下是Java实现归并排序的示例代码：

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {8, 5, 1, 6, 3, 2, 7, 4};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

上述代码首先定义了一个包含八个整型元素的数组。然后，执行了归并函数，将序列一分为二，分别排序后再合并，最终将数组输出。

结论

以上是Java实现五种常见的排序算法的示例代码。无论是初学者还是高级开发者，都应该熟练掌握这些算法，因为它们是计算机科学中最重要的基础问题之一。

阅读剩余 80%