912.排序数组

[hey-monster]

给你一个整数数组 nums，请你将该数组升序排列。

 

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
 

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/* 冒泡 */

void swap(int* a, int* b){
    int tmp = *(int*)a;
    *(int*)a = *(int*)b;
    *(int*)b = tmp;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    for(int i = numsSize - 1; i > 0; --i){
        int flag = 0;
        for(int j = 0; j < i; ++j){
            if(nums[j] > nums[j+1]){
                swap(&nums[j], &nums[j+1]);
                flag = 1;
            }
        }
        if(flag == 0){
            break;
        }
    }
    *returnSize = numsSize;
    return nums;
}

/* 插入排序 */

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

/* 希尔排序 */

void swap(int* a, int* b){
    int tmp = *(int*)a;
    *(int*)a = *(int*)b;
    *(int*)b = tmp;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    for(int D = numsSize / 2; D > 0; D /= 2){       //希尔增量序列
        for(int Pos = D; Pos < numsSize; ++Pos){    //插入排序
            int tmp = nums[Pos];
            int i;
            for(i = Pos; i >= D && nums[i - D] > tmp; i -= D){
                swap(&nums[i], &nums[i - D]);
            }
            nums[i] = tmp;
        }
    }
    *returnSize = numsSize;
    return nums;
}

/* 堆排序 */

void swap(int* a, int* b){
    int tmp = *(int*)a;
    *(int*)a = *(int*)b;
    *(int*)b = tmp;
}
void PercDown(int* nums, int top, int maxIndex){
    int Parent, Child;
    for(Parent = top; (Parent * 2 + 1) <= maxIndex; Parent = Child){
        Child = Parent * 2 + 1;
        if(Child != maxIndex && nums[Child] < nums[Child + 1]){
            Child++;
        }
        if(nums[Parent] > nums[Child]){
            break;
        }else{
            swap(&nums[Parent], &nums[Child]);
        }
    }
}
void HeapPrint(int* heap, int size){
    for(int i = 0; i <= size; ++i){
        printf(" %d \n", heap[i]);
    }
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    int top = numsSize/2 - 1; 
    for(int i = top; i >= 0; --i){
        PercDown(nums, i, numsSize - 1);    //调成树
        //HeapPrint(nums, numsSize - 1);
    }
    //HeapPrint(nums, numsSize - 1);
    for(int i = numsSize - 1; i >= 0; --i){
        swap(&nums[0], &nums[i]);
        PercDown(nums, 0, i - 1);
    }
    *returnSize = numsSize;
    return nums;
}

快速排序

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
/* 堆排序 */
void swap(int* a, int* b){
    int tmp = *(int*)a;
    *(int*)a = *(int*)b;
    *(int*)b = tmp;
}
int g_cutoff = 100;
void Insertion_Sort(int* nums, int size){
    for(int i = 1; i < size; ++i){
        int tmp = nums[i];
        int j;
        for( j = i; j > 0 && nums[j - 1] > tmp; --j){
            nums[j] = nums[j - 1];
        }
        nums[j] = tmp;
    }
}
int Median3(int* nums, int left, int right){
    int Center = (left + right)/2;
    if(nums[left] > nums[Center]){
        swap(&nums[left], &nums[Center]);
    }
    if(nums[left] > nums[right]){
        swap(&nums[left], &nums[right]);
    }
    if(nums[Center] > nums[right]){
        swap(&nums[Center], &nums[right]);
    }
    //移到右边
    swap(&nums[Center], &nums[right - 1]);
    return nums[right - 1];
}
void Quick_Sort(int* nums, int left, int right){
    if(g_cutoff <= right - left){
        int Pivot = Median3(nums, left, right);
        int i = left;
        int j = right - 1;
        for(;;){
            while(nums[++i] < Pivot){}
            while(nums[--j] > Pivot){}
            if(i < j){
                swap(&nums[i], &nums[j]);
            }else{
                break;
            }
        }
        swap(&nums[i], &nums[right - 1]);
        Quick_Sort(nums, left, i - 1);
        Quick_Sort(nums, i + 1, right);
    }else{
        Insertion_Sort(nums + left, right - left + 1);
    }
}
void quickSort(int* nums, int N){
    Quick_Sort(nums, 0, N - 1);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    quickSort(nums, numsSize);
    *returnSize = numsSize;
    return nums;
}