快速排序三数取中

发表于 | 更新于

给一个有序的数组，那代码的时间复杂度就是O(n^2)拉。
最好就是取一个要排序数组中所有值的中值，（很难）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:

    int partition(vector<int>& nums, int left, int right) {
       
       int mid = (left + right) / 2;
        if (nums[left] > nums[right]) 
            swap(nums[left], nums[right]);
        if (nums[mid] > nums[right])
            swap(nums[mid], nums[right]);
        if (nums[mid] > nums[left])
            swap(nums[mid], nums[left]);                //把中值换到最左边
        
        int val = nums[left];   
        int i = left, j = right;                        //填坑法
        while (i < j) {
           while (i < j && nums[j] >= val) j--;
           nums[i] = nums[j]; 
           while (i < j && nums[i] <= val) i++;
            nums[j] = nums[i];
        }
        nums[i] = val; 
        return i;
    }
 
    void sort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        int mid = partition(nums, left, right);
        sort(nums, left, mid-1);
        sort(nums, mid + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

没有优化的快排贴一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}