各种排序算法

 void QuickSort(vectorint>& nums, int lo, int hi){
        if(lo  hi){
            int p = partition(nums,lo,hi);
            QuickSort(nums,lo,p-1);
            QuickSort(nums,p+1,hi);
        }
    }
    int partition(vectorint>& nums, int lo, int hi){
        int pivot = nums[lo];
        while(lo  hi){
            while( lo  pivot) --hi;
            nums[lo] = nums[hi];//小的放左边
            while( lo lo;
            nums[hi] = nums[lo];//大的放右边
        }
        nums[lo] = pivot;//pivot放中间
        return lo;
    }

void InsertSort(vectorint>& nums){
        int n = nums.size();
        for(int i = 1; i){
            int t = nums[i];//先取出nums[i]
            int j = i;
            while( j > 0 && nums[j-1] > t){
                nums[j] = nums[j-1];
                j--;
            }
            //找到正确的位置
            nums[j] = t;
        }
    }

 void ShellSort(vectorint>& nums){
        int n = nums.size();
        for(int k = n/2; k >= 1; k/=2){
            // InsertSort
            for(int i = k; i ){
                int t = nums[i];
                int j = i;
                while(j - k >= 0 && nums[j-k] > t){
                    nums[j] = nums[j-k];
                    j -= k;
                }
                nums[j] = t;
            }
        }
    }

 void merge(vectorint>& nums,int lo, int hi){
        int mid = (lo+hi)/2;
        vectorint> temp;
        int i = lo, j = mid+1;
        while(i  hi){
            if(nums[i] ]);
            else temp.push_back(nums[j++]);
        }
        while(i ]);
        while(j ]);
        for(int i = lo; i )
            nums[i] = temp[i-lo];
    }
    void MergeSort(vectorint>& nums, int lo, int hi){
        if(lo >= hi) return;
        int mid = (lo + hi)/2;
        MergeSort(nums,lo,mid);
        MergeSort(nums,mid+1,hi);
        merge(nums,lo,hi);
    }

void percdown(vectorint>& nums, int n, int index){
        int t = nums[index];// 先取出index处的值
        int pa = index, chi;
        while(pa*2+1  n){
            chi = pa*2 + 1;
            if(chi != n-1 && nums[chi] 1])
                chi++;
            if(t >= nums[chi]) break;//找到了正确的位置
            nums[pa] = nums[chi];
            pa = chi;//
        }
        nums[pa] = t;//把t放在正确的位置上
    }
    void HeapSort(vectorint>& nums){
        int n = nums.size();
        //建堆
        for(int i = n/2-1; i >= 0; i--)
            percdown(nums,n,i);
        for(int i = n-1; i >= 1; i--){
            //把最大的放在最后
            swap(nums[0],nums[i]);
            //调整交换后这个值的位置
            percdown(nums,i,0);
        }
    }