Sorting algorithm, the basic point is the interview must be tested, the personal summary of some sorting algorithm implementation, write some personal understanding, I do not know whether to write wrong <_<

1. Bubble sort

  • From the starting point, the size of the two adjacent members is compared, and if the condition is met, the positions are switched until the entire traversal is complete 
    void TestSort::BubbleSort(int* arr, int size)
{
    if (arr == nullptr) {
        return;
    }

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j]; arr[j] = tmp; }}}}Copy the code

2. Select sort

  • The first time, from a[1] ~ a[n-1]Find the minimum and then follow a[0]Compare, if less than a[0], the exchange
  • The second time, from a[2] ~ a[n-1]Find the minimum and then follow a[1]Compare, if less than a[1], the exchange
  • .
  • N minus 1. Compare a[n-2] 和 a[n-1]If the latter is less than the former, then swap 
    void TestSort::SelectSort(int* arr, int size)
{
    if (arr == nullptr) {
        return;
    }

    for (int i = 0; i < size - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < size; ++j) {
            if(arr[j] < arr[i]) { min = j; }}if(i ! = min) {inttmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; }}}Copy the code

3. Insertion sort

  • The main idea is to construct an ordered sequence over time
  • from a[0]Start, and then go a[1] 跟 a[0]Compare, if less than, then swap
  • At this timea[0], a[1]Is an ordered sequence
  • Then there isa[2] 在 a[0], a[1]To find the right position
  • untila[n-1] 在 a[0] ... a[n-2]To find the right position 
    void TestSort::InsertSort(int* arr, int size)
{
    if (arr == nullptr || size <= 1) {
        return;
    }

    for (int i = 1; i < size; ++i) {
        int j = i;
        int tmp = arr[i];
        while (j >= 1 && arr[j - 1] >= tmp) {
            arr[j] = arr[j - 1];
            --j;
        }

        if(i ! = j) { arr[j] = tmp; }}}Copy the code

Merge sort

  • Divide the array evenly into left and right parts, and repeat until you have 1 member
  • Then start merging the left and right arrays into an ordered sequence
  • Then go back up and merge the left and right ordered sequences again, making them an ordered sequence until you get back to the top 
    void TestSort::Merge(int* arr, int low, int mid, int high)
{
    int old = low;
    const int size = high - low + 1;
    int* tmp = new int[size];
    memset(tmp, 0.sizeof(int) * size);

    // Merge the left and right arrays
    int mrg = mid + 1;
    int index = 0;
    while (low <= mid && mrg <= high) {
        if (arr[low] < arr[mrg]) {
            tmp[index++] = arr[low++];
        } else{ tmp[index++] = arr[mrg++]; }}// The left
    while (low <= mid) {
        tmp[index++] = arr[low++];
    }

    // The rest on the right
    while (mrg <= high) {
        tmp[index++] = arr[mrg++];
    }

    / / assignment
    memcpy(&arr[old], tmp, sizeof(int) * size);
    delete tmp;
}

void TestSort::MergeSort(int* arr, int low, int high)
{
    if (arr == nullptr || low >= high) {
        return;
    }

    int mid = (low + high) / 2;
    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, high);
    Merge(arr, low, mid, high);
}
Copy the code

5. Heap sort

  • The main use of binary heap top maximum or minimum characteristics to sort
  • We build the array into a binary heap, where the top of the heap is the maximuma[n-1]Student: Swap, at this pointa[n-1]Is ordered
  • Because after the swap, the top of the heap is not the maximum, so you need to adjust the binary heap, move the largest of the remaining members to the top of the heap, and then suma[n-2]Student: Swap, at this pointa[n-2] a[n-1]Is ordered
  • Repeat until the last one
  • In fact, the so-called creating a binary heap and adjusting the binary heap, are moving members to make the top of the heap to the maximum or minimum value, the operation is the same method, is to compare the parent node and child nodes, and then put the maximum value on the parent node, and then recursively to the bottom 
    void TestSort::HeapMax(int* arr, int size, int index)
{
    int left = (2 * index) + 1;
    int right = left + 1;
    int max = index;
    
    // Compare the left child node
    if (left < size && arr[left] > arr[index]) {
        max = left;
    }

    // Compare the right child node
    if (right < size && arr[right] > arr[max]) {
        max = right;
    }

    / / exchange
    if(index ! = max) {Swap(arr[index], arr[max]);
        HeapMax(arr, size, max); }}void TestSort::HeapSort(int *arr, int size)
{
    if (arr == nullptr || size <= 0) {
        return;
    }

    // Create a large root heap
    int indexLast = size - 1;
    int indexStart = (indexLast - 1) / 2;
    for (int i = indexStart; i >= 0; --i) {
        HeapMax(arr, size, i);
    }

    // Sort the large root heap
    for (int i = size - 1; i >= 0; --i) {
        Swap(arr[0], arr[i]);
        HeapMax(arr, i, 0); }}Copy the code

Quick sort

  • witha[0]To do the split, to split the array to the lefta[0] ~ a[mid]And the righta[mid+1] ~ a[n-1]
  • Then recursively do the above on both sides until the array is split to 1 member
  • And then the idea of writing the code is
    • If the index of the first part of the array is low, the index of the last part of the array is high
    • witha[0]Let’s compare. Let’s saytmp = a[0]
    • thenhighTo start, inlow < highStudent: Ifa[high]Greater than or equal totmp,--high, otherwise,a[low] = a[high]
    • thenlowTo start, inlow < highStudent: Ifa[low]Less than or equal totmp,++low, otherwise,a[high] = a[low]
    • untillow == high.a[low] = tmp, the array is split into left and right, lefta[low] ~ a[mid]They’re all less than or equal totmp 的
    • The right of thea[mid+1] ~ a[high]Is greater thantmp 的
    • Do the same for both arrays until the array is split to only one member
    int TestSort::GetIndex(int* arr, int low, int high)
{
    if (arr == nullptr) {
        return - 1;
    }

    int tmp = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= tmp) {
            --high;
        }

        if (low >= high) {
            break;
        } else {
            arr[low] = arr[high];
        }

        while (low < high && arr[low] <= tmp) {
            ++low;
        }

        if (low >= high) {
            break;
        } else {
            arr[high] = arr[low];
        }
    }

    arr[low] = tmp;
    return low;
}

void TestSort::QuickSort(int* arr, int low, int high)
{
    if (low >= high) {
        return;
    }

    int index = GetIndex(arr, low, high);
    if (index == - 1) {
        return;
    }

    QuickSort(arr, low, index - 1);
    QuickSort(arr, index + 1, high);
}
Copy the code