Java常用的八种排序算法与代码实现

在Java中，排序算法是非常重要的基础知识，掌握常用排序算法不仅可以提高程序员的知识水平，也可以在以后的工作中提高效率。本文将详细讲解八种Java常用排序算法的原理和代码实现。

冒泡排序（Bubble Sort）

冒泡排序也是常用的排序算法之一，其基本思想是通过比较两个相邻的元素，如果他们的顺序不对则交换他们直至序列变得有序。这里给出冒泡排序的Java代码实现。

public static void bubbleSort(int[] arr){
    int n = arr.length;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                //交换两数
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

选择排序（Selection Sort）

选择排序也是常用的排序算法之一，其基本思想是在未排序的数据中找到最小（大）的数据，将其放在序列的起始位置作为已排序数据，然后从余下的未排序数据中重复上述操作直至整个序列有序。这里给出选择排序的Java代码实现。

public static void selectionSort(int[] arr){
    int n = arr.length;
    for(int i=0;i<n-1;i++){
        int minIndex = i;
        for(int j=i+1;j<n;j++){
            if(arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        //交换当前元素和最小元素
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

插入排序（Insertion Sort）

插入排序也是常用的排序算法之一，其基本思路是将一个数据插入到已排序好的有序序列中,从而得到一个新的，个数加一的有序序列。这里给出插入排序的Java代码实现。

public static void insertionSort(int[] arr){
    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--;
        }
        arr[j+1] = key;
    }
}

希尔排序（Shell Sort）

希尔排序也是常用的排序算法之一，它是插入排序的进化版，通过将数据按一定间隔分组，对每组数据执行插入排序，随着间隔逐渐减小，数据会越来越接近有序状态。最后对所有数据再执行一次插入排序，完成排序。这里给出希尔排序的Java代码实现。

public static void shellSort(int[] arr){
    int n = arr.length;
    //设置增量gap
    for(int gap=n/2;gap>0;gap/=2){
        //对每个分组进行插入排序
        for(int i=gap;i<n;i++){
            int temp = arr[i];
            int j = i-gap;
            while(j>=0 && arr[j]>temp){
                arr[j+gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = temp;
        }
    }
}

快速排序（Quick Sort）

快速排序也是常用的排序算法之一，它通过将一个数组分成两个子数组，然后递归排序两个子数组，完成对数组的排序。这里给出快速排序的Java代码实现。

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

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

归并排序（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, j = mid + 1, 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++];
    }
    for (int p = 0; p < temp.length; p++) {
        arr[left + p] = temp[p];
    }
}

堆排序（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 j=n-1;j>0;j--){
        //交换堆顶元素和未排序区的末尾元素
        int temp = arr[0];
        arr[0] = arr[j];
        arr[j] = temp;
        //调整未排序区构造新的堆
        adjustHeap(arr,0,j);
    }
}

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+1] > arr[k]){
            k++;
        }
        if(arr[k] > temp){
            arr[i] = arr[k];
            i = k;
        }else{
            break;
        }
        arr[i] = temp;
    }
}

计数排序（Counting Sort）

计数排序也是常用的排序算法之一，其基本思想是对于每一个非负整数 x，在数组中找出小于等于 x 的元素个数，然后利用这个信息将元素直接放到正确的位置上。这里给出计数排序的Java代码实现。

public static void countingSort(int[] arr){
    int min = arr[0];
    int max = arr[0];
    for(int i=1;i<arr.length;i++){
        if(arr[i]<min){
            min = arr[i];
        }
        if(arr[i]>max){
            max = arr[i];
        }
    }
    int[] countArr = new int[max-min+1];
    for(int i=0;i<arr.length;i++){
        countArr[arr[i]-min]++;
    }
    int index = 0;
    for(int i=0;i<countArr.length;i++){
        while(countArr[i]>0){
            arr[index++] = i+min;
            countArr[i]--;
        }
    }
}

总结

本文详细讲解了Java常用的八种排序算法及代码实现，包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序和计数排序，这些算法都有其特点和适用场景，程序员应根据实际情况选择合适的算法来实现排序操作。