讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析
共 3 个回复
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {

        if(nums.size() <=1)  //排除空或者只有一个的情况;
        {
            return nums;
        }

        int size = nums.size();
        vector<int> D;
        //计算分组参数;
        while(1 != size)
        {
            size = size/2;
            D.push_back(size);
        }


        int temp = 0;
        for(int i = 0; i < D.size();i++)  //依次使用每个分组参数;
        {
            for(int j = 0; j < D[i]; j++)  //对于分组完成后的每个序列;
            {
                int counter = ((nums.size()%D[i]) ? (nums.size()/D[i]) : (nums.size()/D[i]-1));  //计算每组个数;
                for(int n = 1; n <= counter; n++)  //进行n次冒泡排序;
                {
                    for(int k = j + D[i] ; k < nums.size(); k=k+D[i])     //进行一次冒泡排序;
                    {
                        if(nums[k-D[i]] > nums[k])
                        {
                            temp = nums[k];
                            nums[k] = nums[k - D[i]];
                            nums[k-D[i]] = temp;
                        }
                    }
                }

            }
        }
        return nums;

    }
};

C++;感觉理解了以后,稍微记一下就完事了

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        shellSort(nums);
        return nums;
    }

    void shellSort(vector<int>& nums){
        for(int gap = nums.size()/2; gap > 0; gap /= 2){
            for(int i = gap;i < nums.size(); i++){
                int currentNum = nums[i];
                int preIndex = i - gap;
                while(preIndex >= 0 && nums[preIndex] > currentNum ){
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = currentNum;
            }
        }
    }

};

希尔排序用python终于可以通过了。虽然耗时仍是很久,但复杂度的确是降低了。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        # 获得最大的gap
        gap = int(length/2)
        # 遍历所有的gap可能
        while gap > 0:
            # i 是分组后第二个数的位置,第一个数的位置均在 0 ~ gap 里
            for i in range(gap,length):
                # 排在最后的数,
                temp = nums[i]
                j = i
                # 要和 j-gap、j-2*gap 等位置的数字比较
                # 如果它们很大,那么就让它们往后错位
                while j >= gap and nums[j-gap] > temp:
                    nums[j] = nums[j-gap]
                    j -= gap
                # 到底了,别忘了加回来temp
                nums[j] = temp
            # 缩小gap的值
            gap = int(gap/2)
        return nums