Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/8.排序.md

8.1 直接插入排序

typedef int ElementType;

void StraightInsertionSort(ElementType Array[], int N) {
    int P, i;
    ElementType tmp;
    for (P = 1; P < N; ++P) {
        tmp = Array[P];
        for (i = P; i > 0 && Array[i - 1] > tmp; ++P) {
            Array[i] = Array[i - 1];
        }
        Array[i] = tmp;
    }
}

8.2 折半插入排序

#include <cstdio>

typedef int ElementType;

void PrintList(ElementType Array[], int N);

void BinaryInsertionSort(ElementType Array[], int N) {
    int low, high, mid;
    ElementType tmp;
    for (int i = 1; i < N; ++i) {
        low = 0;
        high = i - 1;
        tmp = Array[i];
        while (low <= high) {
            mid = (low + high) / 2;
            if (tmp < Array[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (int j = i; j > high + 1; --j) {
            Array[j] = Array[j - 1];
        }
        Array[high + 1] = tmp;
    }
    PrintList(Array, N);
}

void PrintList(ElementType Array[], int N) {
    printf("[");
    for (int i = 0; i < N; ++i) {
        if (i == N - 1) {
            printf("%d", Array[i]);
        } else {
            printf("%d, ", Array[i]);
        }
    }
    printf("]\n");
}

int main() {
    ElementType Array[] = {10, 25, 6, 8, 75, 65, 15, 36, 54, 98};
    int length = sizeof(Array) / sizeof(int);
    PrintList(Array, length);
    BinaryInsertionSort(Array, length);
}

8.3 希尔排序

  插入排序的一种

#include <cstdio>

typedef int ElementType;

void PrintList(ElementType Array[], int N) {
    printf("[");
    for (int i = 0; i < N; ++i) {
        if (i == N - 1) {
            printf("%d", Array[i]);
        } else {
            printf("%d, ", Array[i]);
        }
    }
    printf("]\n");
}

//取H(0)=N/2,H(k-1)=H(k)/2为增量序列
void ShellSort(ElementType Array[], int N) {
    int i, j, Increment;
    ElementType tmp;
    for (Increment = N / 2; Increment > 0; Increment /= 2) {
        printf("%d :\n", Increment);
        for (i = Increment; i < N; ++i) {
            tmp = Array[i];
            for (j = i; j >= Increment; j -= Increment) {
                if (tmp < Array[j - Increment]) {
                    Array[j] = Array[j - Increment];
                } else {
                    break;
                }
            }
            Array[j] = tmp;
            PrintList(Array, N);
        }
    }
    PrintList(Array, N);
}


int main() {
    ElementType Array[] = {10, 25, 6, 8, 75, 65, 15, 36, 54, 98};
    int length = sizeof(Array) / sizeof(int);
    PrintList(Array, length);
    ShellSort(Array, length);
}

8.4 冒泡排序

#include <cstdio>

typedef int ElementType;

void PrintList(ElementType Array[], int N) {
    printf("[");
    for (int i = 0; i < N; ++i) {
        if (i == N - 1) {
            printf("%d", Array[i]);
        } else {
            printf("%d, ", Array[i]);
        }
    }
    printf("]\n");
}

void Swap(ElementType *x, ElementType *y) {
    ElementType tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

void BubbleSort(ElementType Array[], int N) {
    int i, j, flag;
    for (i = 0; i < N - 1; ++i) {//N个数据，需要循环N-1次。数据下标为从0开始条件即为i = 0; i < N - 1; (如果数据下标为从1开始，即为i = 1; i <= N - 1)
        flag = 0;
        for (j = 0; j < N - (i + 1); ++j) {//数据下标为从0开始条件即为j = 0; j < N - (i + 1); (如果数据下标为从1开始，即为j = 1; j <= N - i;)
            // [即总共N个数据，需要在第i次比较N-i次]
            if (Array[j] > Array[j + 1]) {
                Swap(&Array[j], &Array[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
    PrintList(Array, N);
}


int main() {
    ElementType Array[] = {10, 25, 6, 8, 75, 65, 15, 36};
    int length = sizeof(Array) / sizeof(int);
    PrintList(Array, length);
    BubbleSort(Array, length);
}

8.5 快速排序

#pragma clang diagnostic push
#pragma ide diagnostic ignored "misc-no-recursion"

#include <cstdio>

typedef int ElementType;

void PrintList(ElementType Array[], int N) {
    printf("[");
    for (int i = 0; i < N; ++i) {
        if (i == N - 1) {
            printf("%d", Array[i]);
        } else {
            printf("%d, ", Array[i]);
        }
    }
    printf("]\n");
}

//快速排序
void QuickSort(ElementType Array[], int low, int high) {
    if (low < high) {
        //此段作用是找出中心点（中心点为第一个点，即low所指位置），并分割
        int x = Array[low];
        while (low < high) {
            while (low < high && Array[high] >= x) // 从右向左找第一个小于x的数
                high--;
            if (low < high)
                Array[low++] = Array[high];

            while (low < high && Array[low] < x) // 从左向右找第一个大于等于x的数
                low++;
            if (low < high)
                Array[high--] = Array[low];
        }
        Array[low] = x;
        //此段作用是找出中心点（中心点为第一个点，即low所指位置），并分割
        QuickSort(Array, low, low - 1); // 递归调用
        QuickSort(Array, low + 1, high);
    }
}

int main() {
    ElementType Array[] = {10, 25, 6, 8, 75, 65, 15, 36};
    int length = sizeof(Array) / sizeof(int);
    PrintList(Array, length);
    QuickSort(Array, 0, length - 1);
    PrintList(Array, length);
}

#pragma clang diagnostic pop