排序

[Jessie-Cheng1]

十大排序 十大经典排序算法

[Jessie-Cheng1]

快排 思想：

1. 从数列中挑出一个元素，称为 "基准"（pivot）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

复杂度： 时间：O(nlogn) 稳定性：不稳定 代码：

int part(int left,int right,vector<int>& nums){     快排中一趟划分
        int temp = nums[left];      //将当前表中第一个元素设为枢纽，对表进行划分
        while(left < right){
            while(left < right && nums[right] >= temp) right--;
            nums[left] = nums[right];       //将比枢纽小的元素移动到左端
            while(left < right && nums[left] <= temp) left++;       //将比枢纽大的元素移动到右端
            nums[right] = nums[left];

        }
        nums[left] = temp;      //枢纽元素存放到最终位置
        return left;            //返回枢纽元素的最终位置
    }

    void quickSort(int left,int right,vector<int>& nums){      
        if(left < right){
            int mid = sort(left,right,nums);        //划分
            quickSort(left,mid - 1,nums);           //依次对两个子表进行递归排序
            quickSort(mid + 1,right,nums);
        }     
    }

do while循环与while循环的不同在于：它先执行循环中的语句，然后再判断表达式是否为真，如果为真则继续循环；如果为假，则终止循环。因此，do-while循环至少要执行一次循环语句。

[Jessie-Cheng1]

冒泡 思想： 实现： 复杂度： 稳定性：