排序算法归集 – 源码巴士

冒泡排序

int *sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int tmp;
        for (int i = 0; i < numsSize; ++i) {
                for (int j = 0; j > numsSize - 1; ++j) {
                        if (nums[j] < nums[j + 1]) {
                                tmp = nums[j];
                                nums[j] = nums[j + 1];
                                nums[j + 1] = tmp;
                        }
                }
        }
        return nums;
}

选择排序

int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int tmp;
        for (int i = 0; i < numsSize - 1; ++i) {
                for (int j = i + 1; j > 0; --j) {
                        if (nums[j] < nums[j - 1]) {
                                tmp = nums[j];
                                nums[j] = nums[j - 1];
                                nums[j - 1] = tmp;
                        }
                }
        }
        return nums;
}

插入排序

int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int tmp, index;
        for (int i = 0; i < numsSize; ++i) {
                tmp = INT_MAX;
                for (int j = i; j < numsSize; ++j) {
                        if (tmp > nums[j]) {
                                tmp = nums[j];
                                index = j;
                        }
                }
                nums[index] = nums[i];
                nums[i] = tmp;
        }
        return nums;
}

堆排序

#define right_tree(i) (2 * i + 1)
#define left_tree(i) (2 * i)
#define parent_tree(i) (i / 2)

void max_heapify(int *s, int i, int nums_size)
{
        if ((i >= nums_size) || (i < 0))
                return;
        int l = left_tree(i);
        int r = right_tree(i);
        int target;
        int tmp;
        if (l >= nums_size)
                return;
        if (r >= nums_size)
                return;
        target = (s[l] > s[i]) ? l : i;
        target = (s[r] > s[target]) ? r : target;

        if (target != i) {
                tmp = s[target];
                s[target] = s[i];
                s[i] = tmp;
                max_heapify(s, target, nums_size);
        }
}

void build_max_heapify(int *s, int nums_size)
{
        for (int j = nums_size/2 - 1; j >= 0; --j) {
                max_heapify(s, j, nums_size);
        }
}

void heap_sort(int *s, int nums_size)
{
        int tmp;
        build_max_heapify(s, nums_size);
        for (int i = nums_size - 1; i > 0; --i) {
                tmp = s[0];
                s[0] = s[i];
                s[i] = tmp;
                max_heapify(s, 0, i);
        }
}

int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        heap_sort(nums, numsSize);
        return nums;
}

归并排序

void merge_sort(int *nums, int nums_size)
{
        int m = nums_size / 2;
        int l_index = 0;
        int r_index = m;
        int n_index = 0;
        int *nums_l = malloc(m * sizeof(int));
        int *nums_r = malloc((nums_size - m) * sizeof(int));
        if ((nums_l == NULL) || (nums_r == NULL))
                return;

        while ((r_index < nums_size) || (l_index < m)) {
                if (l_index < m)
                        nums_l[l_index] = nums[l_index];
                if (r_index < nums_size)
                        nums_r[r_index - m] = nums[r_index];
                r_index++;
                l_index++;
        }
        l_index = 0;
        r_index = 0;
        n_index = 0;
        while ((r_index < nums_size) || (l_index < m)) {
                if (n_index >= nums_size) {
                        break;
                }

                if ((l_index < m) && (r_index < nums_size - m)) {
                        if (nums_l[l_index] < nums_r[r_index]) {
                                nums[n_index++] = nums_l[l_index++];
                        } else {
                                nums[n_index++] = nums_r[r_index++];
                        }
                } else if (l_index < m) {
                        nums[n_index++] = nums_l[l_index++];
                } else if (r_index < nums_size) {
                        nums[n_index++] = nums_r[r_index++];
                } else {
                        break;
                }
        }
}

void sort_array(int *nums, int nums_size)
{
        int m = nums_size / 2;
        if (nums_size > 1) {
                sort_array(nums, m);
                sort_array(nums + m, nums_size - m);
                merge_sort(nums, nums_size);
        }
}

int* asortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        sort_array(nums, numsSize);
        return nums;
}

计数排序(待排序数只能大于零)

int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int *A = calloc(numsSize, sizeof(int));
        int nums_max = INT_MIN;
        for (int i = 0; i < numsSize; ++i) {
                if (nums[i] > nums_max)
                        nums_max = nums[i];
        }
        int *B = calloc(nums_max + 1, sizeof(int));
        for (int i = 0; i < numsSize; ++i)
                B[nums[i]] += 1;
        for (int i = 1; i <= nums_max; ++i)
                B[i] += B[i - 1];

        for (int i = numsSize - 1; i >= 0; --i) {
                A[B[nums[i]]-1] = nums[i];
                B[nums[i]] -= 1;
        }
        return A;
}

计数排序(待排序数可以小于零)

1). 
int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int *A = calloc(numsSize, sizeof(int));
        int nums_max = INT_MIN;
        int nums_min = INT_MAX;
        for (int i = 0; i < numsSize; ++i) {
                if (nums[i] > nums_max) {
                        nums_max = nums[i];
                }
                if (nums[i] < nums_min) {
                        nums_min = nums[i];
                }
        }
        if (nums_min < 0)
                nums_max = nums_max - nums_min;

        int *B = calloc(nums_max + 1, sizeof(int));
        for (int i = 0; i < numsSize; ++i) {
                if (nums_min < 0)
                        nums[i] -= nums_min;
                B[nums[i]] += 1;
        }
        for (int i = 1; i <= nums_max; ++i)
                B[i] += B[i - 1];
        for (int i = numsSize - 1; i >= 0; --i) {
                A[B[nums[i]]-1] = nums[i];
                B[nums[i]] -= 1;
        }

        if (nums_min < 0) {
                for (int i = 0; i < numsSize; ++i)
                        A[i] += nums_min;
        }
        return A;
}

2).
int* sortArray(int* nums, int numsSize, int* returnSize)
{
        *returnSize = numsSize;
        int *A = calloc(numsSize, sizeof(int));
        int nums_max = INT_MIN;
        int nums_min = INT_MAX;
        for (int i = 0; i < numsSize; ++i) {
                if (nums[i] > nums_max) {
                        nums_max = nums[i];
                }
                if (nums[i] < nums_min) {
                        nums_min = nums[i];
                }
        }
        if (nums_min < 0)
                nums_max = nums_max - nums_min;
        else 
                nums_min = 0;

        int *B = calloc(nums_max + 1, sizeof(int));
        for (int i = 0; i < numsSize; ++i)
                B[nums[i] - nums_min] += 1;
        
        for (int i = 1; i <= nums_max; ++i)
                B[i] += B[i - 1];

        for (int i = numsSize - 1; i >= 0; --i) {
                A[B[nums[i] - nums_min]-1] = nums[i];
                B[nums[i] - nums_min] -= 1;
        }
        free(B);
        return A;
}

原文链接：https://blog.csdn.net/qq_28217563/article/details/106562649