常用排序算法

• 目录
• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 快速排序
• 归并排序
• 堆排序
• 致谢

1. 冒泡排序

C实现，从小到大

void bubble_sort(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

2. 选择排序

C实现，从小到大

void selection_sort(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        int min = i;
        for (int j = i+1; j < length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
            arr[i] = arr[min] + arr[i];
            arr[min] = arr[i] - arr[min];
            arr[i] = arr[i] - arr[min];
        }
    }
}

3. 插入排序

C实现，从小到大

void insertion_sort(int arr[], int length) {
    int j;
    for (int i = 1; i < length; i++) {
        if (arr[i] < arr[i-1]) {
            int temp = arr[i];
            for (j = i-1; j >= 0 && temp < arr[j]; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
}

4. 希尔排序

C实现，从小到大

void shell_sort(int arr[], int length) {
    int increment = length;
    int k;
    do {
        increment = increment/3+1;
        for (int i = 0; i < increment; i++) {
            for (int j = i+increment; j < length; j+=increment) {
                if (arr[j] < arr[j-increment]) {
                    int temp = arr[j];
                    for (k = j-increment; k >= 0 && temp < arr[k]; k-=increment) {
                        arr[k+increment] = arr[k];
                    }
                    arr[k+increment] = temp;
                }
            }
        }
    } while (increment > 1);
}

5. 快速排序

C实现，从小到大

void quick_sort(int arr[], int start, int end) {
    int i = start;
    int j = end;
    int temp = arr[start]; 
    if (i < j) {
        while (i < j) {
            while (i < j && arr[j] > temp) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i< j && arr[i] < temp) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = temp;
        quick_sort(arr, start, i-1);
        quick_sort(arr, i+1, end);
    }
}

6. 归并排序

C实现，从小到大

void __my_merge(int arr[], int start, int mid, int end, int *temp) {
    int i_start = start;
    int i_end = mid;
    int j_start = mid+1;
    int j_end = end;
    int length = 0;
    while (i_start <= i_end && j_start <= j_end) {
        if (arr[i_start] < arr[j_start]) {
            temp[length] = arr[i_start];
            length++;
            i_start++;
        } else {
            temp[length] = arr[j_start];
            length++;
            j_start++;
        }
    }
    while (i_start <= i_end) {
        temp[length] = arr[i_start];
        length++;
        i_start++;
    }
    while (j_start <= j_end) {
        temp[length] = arr[j_start];
        length++;
        j_start++;
    }
    for (int i = 0; i < length; i++) {
        arr[start+i] = temp[i];
    }
}

void merge_sort(int arr[], int start, int end, int *temp) {
    if (start >= end) {
        return;
    }
    int mid = (start+end)/2;
    merge_sort(arr, start, mid, temp);
    merge_sort(arr, mid+1, end, temp);
    __my_merge(arr, start, mid, end, temp);
}

7. 堆排序

C实现，从小到大

void heap_adjust(int arr[], int index, int length) {
    int max = index;
    int left_child = max*2+1;
    int right_child = max*2+2;
    if (left_child < length && arr[left_child] > arr[max]) {
        max = left_child;
    }
    if (right_child < length && arr[right_child] > arr[max]) {
        max = right_child;
    }
    if (max != index) {
        int temp = arr[max];
        arr[max] = arr[index];
        arr[index] = temp;
        heap_adjust(arr, max, length);
    }
}
void heap_sort(int arr[], int length) {
    for (int i = length/2-1; i >= 0; i--) {
        heap_adjust(arr, i, length);
    }
    for (int i = length-1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heap_adjust(arr, 0, i);
    }
}

不定期更新 不合适的地方 还请指点~ 感激不尽