您现在的位置是：首页 >技术教程 >手撕排序算法代码网站首页技术教程

手撕排序算法代码

今天把学过的代码手动敲了几遍，这里用的是java代码，但是无论什么语言，代码的核心逻辑都是一样的。

1.选择排序

每次从待排序的序列中选择最小（或最大）元素，将其放到已排序序列的末尾（或开头）。这个过程重复进行，直到所有元素排序完成。

public static void selectionSort(int []arr){
    if(arr == null || arr.lengthg < 2){
        return;
    }
    for(int i = 0;i < arr.length - 1;i ++){
        int minIndex = i;
        for(int j = i + 1;j < arr.length;j ++){
            minIndex = arr[j] < arr[minIndex] ? j :minIndex;
        }
        swap(arr,i,minIndex)
    }
}

2.插入排序

将待排序的元素逐个插入到已排序的部分中，直到整个序列有序。

public static void InsertSort(int []arr){
    if(arr == null || arr.length < 2){
        return ;
    }
    for(int i = 1;i < arr.lenmgth;i++){
        for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j --){
            swap(arr,j,j+1);
        }
      }
}

3.冒泡排序

通过重复地交换相邻的元素，使得较大的元素逐渐“浮”到数组的右端，而较小的元素“沉”到数组的左端。通过多次遍历，直到整个数组有序。

public static void bubbleSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }for(int = arr.length -1;e>0;e--){
        for(int i = 0;i < e;i ++){
            if(arr[i]>arr[i+1]{
                swap(arr,i,i+1);
            }
        }
}

4.归并排序

将一个大的问题分解为多个较小的问题，通过递归的方式逐步解决，最后将解决方案合并起来，从而实现排序。归并排序的时间复杂度是 O(n log n)，在所有排序算法中比较稳定且高效，适用于大数据量的排序。

public static void mergeSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    process(arr,0,arr.length-1);
}

public static void process(int[] arr,int L,int R){
    if(L == R){
        return;
    }
    int mid = L + ((R - L)>>1);
    process(arr,L,mid);
    process(arr,mid+1,R);
    merge(arr,L,mid,R);
}

public static void merge(int []arr,int L,int M,int R){
    int[] help = new int[R-L+1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while(p1 <= M && p2 <= R){
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while(p1 <= M){
        help[i++] = arr[p1++];
    }
    while(p2 <= R){
        help[i++] = arr[p2++];
    }
    for(int j = 0; j < help.length ;j ++){
            arr[L+j] = help[j];
       }
}

5.快速排序

通过一个“分区”操作，将数组分成两部分，其中一部分所有元素都小于基准元素，另一部分所有元素都大于基准元素，然后再分别对这两部分继续递归地进行快速排序。

 public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

  
    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
         
            swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R); 
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }


    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

 
    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R;
        while (L < more) {
            if (arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            } else if (arr[L] > arr[R]) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        swap(arr, more, R);
        return new int[] { less + 1, more };
    }

6.堆排序

通过构建一个最大堆或最小堆，使得堆顶元素是整个堆中的最大（或最小）元素，然后不断将堆顶元素与堆的最后一个元素交换，减小堆的有效大小，重新调整堆，直到排序完成。

public static void headInsert(int[] arr,int index){
    while(arr[index] > arr[(i-1)/2]){
        swap(arr,index,(index-1)/2);
        index = (index - 1)/2;
    } 
}

public static void heapify(int[] arr,int index,int heapSize){
    int left = index*2 + 1;
    while(left < heapSize){
        int largest = left + 1 < heapSize && arr[left+1] > arr[left];
        ? left+1 : left;
        
        largest = arr[largest] > arr[index] ? largest : index;
        
        if(largest == index){
            break;
        }
        swap(arr,largest,index);
        index = largest;
        left = index * 2 + 1;
    }
}

public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        retrun ;
    }
    for(int i = 0;i < arr.lebngth;i++){
        heapInsert(arr,i);
    }
    int heapSize = arr.length;
    swap(arr,0,--heapSize);
    while(heapSize > 0){
        heapify(arr,0,heapSize);
        swap(arr,0,--heapSize);
    }
}

7.桶排序
将数据分到有限数量的桶中，然后每个桶内的数据再单独进行排序，最后将各个桶中的数据合并得到最终结果。

 public static void radixSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }


    public static int maxbits(int[] arr)
    {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }


    public static void radixSort(int[] arr, int L, int R, int digit)
    {
        final int radix = 10;
        int i, j = 0;
        int[] bucket = new int[R - L + 1];

        for (int d = 1; d <= digit; d++) {
            int[] count = new int[radix];
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static int getDigit(int x, int d)
    {
        return ((x / ((int)Math.pow(10, d - 1))) % 10);
    }