转载

排序算法总结

  • 插入排序
    稳定排序, 复杂度 n^2
public static void insertSort(int []arr) {
        int i = 0, j = 0, temp = 0;
        for(i = 0; i < arr.length - 1; i++)
            for(j = i + 1; j > 0; j--) {
                if(arr[j] >= arr[j-1]) break;
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
    }
  • 快速排序
    不稳定排序, 复杂度nlog(n)
public static void  swap(int indexOne, int indexTwo, int []arr) {
        int temp = 0;
        temp = arr[indexOne];
        arr[indexOne] = arr[indexTwo];
        arr[indexTwo] = temp;
    }
public static void quickSort(int start, int end, int []arr) {
    if(start >= end) return;
    int mid = arr[start], left = start + 1, right = end;

    while(left < right) {
        while(arr[right] >= mid && left < right) right--;
        while(arr[left] <= mid && left < right) left++;
        swap(left, right, arr);
    }
    if(arr[right] < mid) swap(start, right, arr);
    else right--;
    quickSort(start, right -1, arr);
    quickSort(right + 1, end, arr);
}
  • 归并排序
    稳定排序,复杂度nlog(n)
public static void mergeSort(int arr[], int result[], int start, int end) {
    if(start >= end) return;
    int mid = (end - start) >> 1;
    int start1 = start, end1 = start + mid;
    int start2 = start + mid + 1, end2 = end;

    mergeSort(arr, result, start1, end1);
    mergeSort(arr, result, start2, end2);

    int k = start;
    while(start1 <= end1 && start2 <= end2) {
        if(arr[start1] <= arr[start2]) result[k++] = arr[start1++];
            else result[k++] = arr[start2++];
    }

    while(start1 <= end1) {
        result[k++] = arr[start1++];
    }

    while(start2 <= end2) {
        result[k++] = arr[start2++];
    }

    for(k = start; k <= end; k++) {
        arr[k] = result[k];
    }
}
正文到此结束
本文目录