561. Array Partition I

题目

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

算法

主要就是排序算法，然后把奇数位加和。
以前经常用最笨的冒泡算法去排序，今天尝试用一下快排，体验到了时间复杂度的不同。
快排：

Time Submitted	Status	Runtime	Memory	Language
a few seconds ago	Accepted	36 ms	9.1 MB	c

冒泡：

Time Submitted	Status	Runtime	Memory	Language
23 minutes ago	Accepted	6356 ms	8.9 MB	c

差距还是蛮大的。
快排思想很简单，每次取第一个元素为基准，然后放在它应该放的位置，左边的都小于它，右边的都大于它，然后右边和左边递归。

代码

void quicksort(int* nums,int left ,int right){
    if(left>right)return;
    int temp = nums[left];
    int i;int j;
    i = left; j = right;
    while(i!=j){
        while(nums[j]>=temp&&i<j)j--;
        while(nums[i]<=temp&&i<j)i++;
        if(i!=j){
            int tmp = nums[i];
            nums[i]=nums[j];
            nums[j] = tmp;
        }
        
    }
    nums[left] = nums[i];
    nums[i] =temp;
    quicksort(nums,left,i-1);
    quicksort(nums,i+1,right);
    
}
int arrayPairSum(int* nums, int numsSize) {
    quicksort(nums,0,numsSize-1);
    
    int i;
    int result=0;
    for(i = 0;i<numsSize;i=i+2){
        result+=nums[i];
    }
    return result;
}