Java数据结构的十大排序

Java数据结构的十大排序攻略

简介

在计算机科学中，排序算法是一种将一串数据按照特定顺序进行排列的方法，其中常见的排序算法有很多种，不同的算法适用于不同的数据类型和数据规模。Java是一种常见的编程语言，也提供了很多实现排序算法的类和方法。

本文将介绍Java数据结构的十大排序算法，分别为：插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、堆排序、计数排序、桶排序和基数排序。并针对每种排序算法进行详细的讲解，介绍算法思路、实现方式、时间复杂度等相关内容。

1. 插入排序（Insertion Sort）

插入排序是一种简单的排序算法，其基本思想是将待排序的元素按照大小依次插入已经有序的序列中。插入排序方法有两种：直接插入排序和希尔排序。

1.1 直接插入排序

直接插入排序的思路是将无序数据插入到已经有序的序列中，从而形成一个更大的有序序列。

以下是Java中直接插入排序的代码示例：

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        int temp = arr[i];
        while (j > 0 && temp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
}

1.2 希尔排序

希尔排序是直接插入排序的一种改进算法，它通过比较距离较远（增量较大）的元素进行排序，使得元素可以快速地到达它们的最终位置。

以下是Java中希尔排序的代码实现示例：

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

2. 选择排序（Selection Sort）

选择排序是一种简单的排序算法，其基本思想是通过比较选出最小的元素，然后将它与第一个位置的元素进行交换，接着在剩下的元素中继续寻找最小的元素，重复这个过程直至排序完成。

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

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

3. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，其基本思想是不断比较相邻的元素，将大的元素向右移动，小的元素向左移动，从而实现排序。

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

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        boolean flag = false;
        for (int j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

4. 快速排序（Quick Sort）

快速排序是一种常见的排序算法，其基本思想是通过分治的思想将待排序的序列分成两个子序列，其中一个子序列的
所有元素都比另一个子序列的所有元素小，然后递归地对两个子序列进行排序。

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

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        while (i <= j && arr[i] < pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    int temp = arr[left];
    arr[left] = arr[j];
    arr[j] = temp;
    return j;
}

5. 归并排序（Merge Sort）

归并排序是一种常见的排序算法，其基本思想是将待排序的序列分成若干个子序列，然后对每个子序列递归地进行排序，最后将各个有序子序列合并成一个有序序列。

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

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 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[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    System.arraycopy(temp, 0, arr, left, temp.length);
}

6. 堆排序（Heap Sort）

堆排序是一种常见的排序算法，其基本思想是将待排序的序列构造成一个大根堆或小根堆，然后将堆顶元素与堆底元素进行交换，接着重新调整堆，如此往复直至排序完成。

以下是Java中堆排序的代码实现示例：

public static void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, i);
    }
}

private static void adjustHeap(int[] arr, int i, int n) {
    int temp = arr[i];
    for (int k = 2 * i + 1; k < n; k = 2 * k + 1) {
        if (k + 1 < n && arr[k] < arr[k + 1]) {
            k++;
        }
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

7. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，其基本思想是通过统计待排序数据中小于每个元素的个数，来确定该元素的位置，从而得到排序结果。

以下是Java中计数排序的代码实现示例：

public static void countingSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, arr[i]);
    }
    int[] count = new int[max + 1];
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
    int[] temp = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int index = count[arr[i]] - 1;
        temp[index] = arr[i];
        count[arr[i]]--;
    }
    System.arraycopy(temp, 0, arr, 0, n);
}

8. 桶排序（Bucket Sort）

桶排序是一种非比较排序算法，其基本思想是将待排序的序列分成若干个桶，然后对每个桶单独进行排序，最终将所有桶中的元素有序地合并成一个序列。

以下是Java中桶排序的代码实现示例：

public static void bucketSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, arr[i]);
    }
    int bucketSize = 10;
    int bucketCount = (max - 1) / bucketSize + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketCount);
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }
    for (int i = 0; i < n; i++) {
        int index = (arr[i] - 1) / bucketSize;
        buckets.get(index).add(arr[i]);
    }
    int cursor = 0;
    for (int i = 0; i < bucketCount; i++) {
        List<Integer> bucket = buckets.get(i);
        Collections.sort(bucket);
        for (Integer num : bucket) {
            arr[cursor++] = num;
        }
    }
}

9. 基数排序（Radix Sort）

基数排序是一种非比较排序算法，其基本思想是将待排序的数字按照权重依次排序，从低位到高位进行排序，最终得到一个有序序列。

以下是Java中基数排序的代码实现示例：

public static void radixSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return;
    }
    int maxDigit = getMaxDigit(arr);
    int mod = 10;
    int div = 1;
    List<List<Integer>> buckets = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
        buckets.add(new ArrayList<>());
    }
    for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
        for (int j = 0; j < n; j++) {
            int digit = (arr[j] % mod) / div;
            buckets.get(digit).add(arr[j]);
        }
        int cursor = 0;
        for (int j = 0; j < 10; j++) {
            List<Integer> bucket = buckets.get(j);
            for (Integer num : bucket) {
                arr[cursor++] = num;
            }
            bucket.clear();
        }
    }
}

private static int getMaxDigit(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int num : arr) {
        max = Math.max(max, num);
    }
    return max == 0 ? 1 : (int) Math.log10(max) + 1;
}

总结

本文介绍了Java数据结构的十大排序算法，这些算法在实际开发应用中都有很广泛的应用。根据不同的数据类型和数据规模，我们可以选择不同的排序算法来实现排序功能。熟练理解和掌握这些算法对于提升编程能力和解决实际问题都有很大的帮助。