八种经典排序算法

以下是八种经典排序算法的介绍，包括它们的基本思想、时间复杂度、稳定性以及代码示例：

1. 插入排序

• 基本思想：每步将一个待排序的元素按其关键码值的大小插入到前面已经排序的部分中，直到全部插入完为止。
• 时间复杂度：最坏和平均情况为O(n²)，最佳情况为O(n)（当数据基本有序时）。
• 稳定性：稳定的排序方法。
• 代码示例：

  public static void insertionSort(int[] array) {  
      int tmp;  
      for (int i = 1; i < array.length; i++) {  
          tmp = array[i];  
          int j = i;  
          for (; j > 0 && array[j - 1] > tmp; j--) {  
              array[j] = array[j - 1];  
          }  
          array[j] = tmp;  
      }  
  }

2. 冒泡排序

• 基本思想：持续比较相邻的元素，如果第一个比第二个大，就交换它们，直到没有任何一对数字需要比较。
• 时间复杂度：最坏和平均情况为O(n²)，最佳情况为O(n)（当数据已经有序时）。
• 稳定性：稳定的排序方法。
• 代码示例：

  public static void bubbleSort(int[] array) {  
      int tmp;  
      boolean flag;  
      for (int i = array.length - 1; i >= 0; i--) {  
          flag = false;  
          for (int j = 0; j < i; j++) {  
              if (array[j] > array[j + 1]) {  
                  tmp = array[j];  
                  array[j] = array[j + 1];  
                  array[j + 1] = tmp;  
                  flag = true;  
              }  
          }  
          if (!flag) break; // 如果没有发生交换，排序完成  
      }  
  }

3. 选择排序

• 基本思想：每次从待排序的数据中选出最小（或最大）的元素，存放在序列的起始位置，直到全部排完。
• 时间复杂度：O(n²)。
• 稳定性：不稳定的排序方法。
• 代码示例：

  public static void selectSort(int[] array) {  
      for (int i = 0; i < array.length - 1; i++) {  
          int min = array[i];  
          int minindex = i;  
          for (int j = i; j < array.length; j++) {  
              if (array[j] < min) {  
                  min = array[j];  
                  minindex = j;  
              }  
          }  
          if (i != minindex) {  
              array[minindex] = array[i];  
              array[i] = min;  
          }  
      }  
  }

4. 希尔排序

• 基本思想：先取一个小于n的整数作为增量，将数据分组并进行插入排序，逐步减小增量，直到增量为1时进行最后的插入排序。
• 时间复杂度：依赖于增量序列，通常为O(n log n)到O(n²)之间。
• 稳定性：不稳定的排序方法。
• 代码示例：

  public static void shellSort(int[] array) {  
      int n = array.length;  
      for (int gap = n / 2; gap > 0; gap /= 2) {  
          for (int i = gap; i < n; i++) {  
              int temp = array[i];  
              int j;  
              for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {  
                  array[j] = array[j - gap];  
              }  
              array[j] = temp;  
          }  
      }  
  }

5. 归并排序

• 基本思想：将数组分成两半，分别对两半进行排序，然后合并已排序的两半。
• 时间复杂度：O(n log n)。
• 稳定性：稳定的排序方法。
• 代码示例：

  public static void mergeSort(int[] array) {  
      if (array.length < 2) return;  
      int mid = array.length / 2;  
      int[] left = Arrays.copyOfRange(array, 0, mid);  
      int[] right = Arrays.copyOfRange(array, mid, array.length);  
      mergeSort(left);  
      mergeSort(right);  
      merge(array, left, right);  
  }  
  
  private static void merge(int[] array, int[] left, int[] right) {  
      int i = 0, j = 0, k = 0;  
      while (i < left.length && j < right.length) {  
          if (left[i] <= right[j]) {  
              array[k++] = left[i++];  
          } else {  
              array[k++] = right[j++];  
          }  
      }  
      while (i < left.length) array[k++] = left[i++];  
      while (j < right.length) array[k++] = right[j++];  
  }

6. 快速排序

• 基本思想：选择一个基准元素，将数组分成两部分，左边部分小于基准，右边部分大于基准，然后递归排序这两部分。
• 时间复杂度：最坏情况为O(n²)，平均情况为O(n log n)。
• 稳定性：不稳定的排序方法。
• 代码示例：

  public static void quickSort(int[] array, int low, int high) {  
      if (low < high) {  
          int pivotIndex = partition(array, low, high);  
          quickSort(array, low, pivotIndex - 1);  
          quickSort(array, pivotIndex + 1, high);  
      }  
  }  
  
  private static int partition(int[] array, int low, int high) {  
      int pivot = array[high];  
      int i = low - 1;  
      for (int j = low; j < high; j++) {  
          if (array[j] < pivot) {  
              i++;  
              int temp = array[i];  
              array[i] = array[j];  
              array[j] = temp;  
          }  
      }  
      int temp = array[i + 1];  
      array[i + 1] = array[high];  
      array[high] = temp;  
      return i + 1;  
  }

7. 堆排序

• 基本思想：利用堆这种数据结构，首先构建一个最大堆，然后将堆顶元素与最后一个元素交换，缩小堆的大小并重新调整堆，直到排序完成。
• 时间复杂度：O(n log n)。
• 稳定性：不稳定的排序方法。
• 代码示例：

  public static void heapSort(int[] array) {  
      int n = array.length;  
      for (int i = n / 2 - 1; i >= 0; i--) {  
          heapify(array, n, i);  
      }  
      for (int i = n - 1; i > 0; i--) {  
          int temp = array[0];  
          array[0] = array[i];  
          array[i] = temp;  
          heapify(array, i, 0);  
      }  
  }  
  
  private static void heapify(int[] array, int n, int i) {  
      int largest = i;  
      int left = 2 * i + 1;  
      int right = 2 * i + 2;  
      if (left < n && array[left] > array[largest]) {  
          largest = left;  
      }  
      if (right < n && array[right] > array[largest]) {  
          largest = right;  
      }  
      if (largest != i) {  
          int swap = array[i];  
          array[i] = array[largest];  
          array[largest] = swap;  
          heapify(array, n, largest);  
      }  
  }

8. 计数排序

• 基本思想：通过统计每个元素出现的次数，然后根据计数结果直接将元素放入正确的位置。
• 时间复杂度：O(n + k)，其中n是待排序元素的数量，k是元素值的范围。
• 稳定性：稳定的排序方法。
• 代码示例：

  public static void countingSort(int[] array) {  
      int max = Arrays.stream(array).max().getAsInt();  
      int[] count = new int[max + 1];  
      for (int num : array) {  
          count[num]++;  
      }  
      int index = 0;  
      for (int i = 0; i < count.length; i++) {  
          while (count[i] > 0) {  
              array[index++] = i;  
              count[i]--;  
          }  
      }  
  }

这些排序算法各有特点，适用于不同的场景和数据规模。在实际应用中，选择合适的排序算法可以显著提高程序的效率。掌握这些算法对于编程和面试都非常重要。