内省排序

选一种语言就能看到代码

def intro_sort(a, lo, hi, depth):
    if hi - lo <= 16:
        insertion_sort_range(a, lo, hi)
        return
    if depth == 0:
        heap_sort_range(a, lo, hi)
        return
    cut = partition(a, lo, hi)
    intro_sort(a, lo, cut, depth - 1)
    intro_sort(a, cut + 1, hi, depth - 1)


def sort(a):
    depth = 2 * max(1, len(a).bit_length())
    intro_sort(a, 0, len(a) - 1, depth)

function introSort(a, lo, hi, depth) {
  if (hi - lo <= 16) {
    insertionSortRange(a, lo, hi);
    return;
  }
  if (depth === 0) {
    heapSortRange(a, lo, hi);
    return;
  }
  const cut = partition(a, lo, hi);
  introSort(a, lo, cut, depth - 1);
  introSort(a, cut + 1, hi, depth - 1);
}

function sort(a) {
  const depth = 2 * Math.ceil(Math.log2(Math.max(2, a.length)));
  introSort(a, 0, a.length - 1, depth);
}

void intro_sort(int a[], int lo, int hi, int depth) {
    if (hi - lo <= 16) {
        insertion_sort_range(a, lo, hi);
        return;
    }
    if (depth == 0) {
        heap_sort_range(a, lo, hi);
        return;
    }
    int cut = partition(a, lo, hi);
    intro_sort(a, lo, cut, depth - 1);
    intro_sort(a, cut + 1, hi, depth - 1);
}

void sort(int a[], int n) {
    int depth = 0;
    while ((1 << depth) < n) depth++;
    intro_sort(a, 0, n - 1, 2 * depth);
}

void intro_sort(std::vector<int>& a, int lo, int hi, int depth) {
    if (hi - lo <= 16) {
        insertion_sort_range(a, lo, hi);
        return;
    }
    if (depth == 0) {
        std::make_heap(a.begin() + lo, a.begin() + hi + 1);
        std::sort_heap(a.begin() + lo, a.begin() + hi + 1);
        return;
    }
    int cut = partition(a, lo, hi);
    intro_sort(a, lo, cut, depth - 1);
    intro_sort(a, cut + 1, hi, depth - 1);
}

void sort(std::vector<int>& a) {
    int depth = 2 * static_cast<int>(std::log2(a.size() + 1));
    intro_sort(a, 0, static_cast<int>(a.size()) - 1, depth);
}

static void IntroSort(int[] a, int lo, int hi, int depth) {
    if (hi - lo <= 16) {
        InsertionSortRange(a, lo, hi);
        return;
    }
    if (depth == 0) {
        HeapSortRange(a, lo, hi);
        return;
    }
    int cut = Partition(a, lo, hi);
    IntroSort(a, lo, cut, depth - 1);
    IntroSort(a, cut + 1, hi, depth - 1);
}

static void Sort(int[] a) {
    int depth = 2 * (int)Math.Ceiling(Math.Log2(Math.Max(2, a.Length)));
    IntroSort(a, 0, a.Length - 1, depth);
}

static void introSort(int[] a, int lo, int hi, int depth) {
    if (hi - lo <= 16) {
        insertionSortRange(a, lo, hi);
        return;
    }
    if (depth == 0) {
        heapSortRange(a, lo, hi);
        return;
    }
    int cut = partition(a, lo, hi);
    introSort(a, lo, cut, depth - 1);
    introSort(a, cut + 1, hi, depth - 1);
}

static void sort(int[] a) {
    int depth = 2 * (32 - Integer.numberOfLeadingZeros(Math.max(2, a.length)));
    introSort(a, 0, a.length - 1, depth);
}