排序之希尔，归并，快排

//希尔排序
//先分组再排序
int shell_sort(int* data, int length){
        int gap = 0;    //步长
        int i = 0, j = 0;
        int temp = 0;
        int seq = 0;
        //分组多少次
        for(gap = length / 2; gap >= 1; gap = gap / 2){
                for(i = gap; i < length; i++){
                        temp = data[i];
                        for(j = i - gap; j >= 0 &&temp < data[j]; j = j - gap){
                                data[j+gap] = data[j];
                        }
                        data[j+gap] = temp;
                }
                printf("sq=%x, gap = %x\n", seq++, gap);
                printarray(data, length);
        }
        return 0;
}

void sort(int *data, int *temp, int start, int middle, int end){
        int i = start, j = middle + 1,k = start;
        while(i <= middle && j <= end){
                if (data[i] > data[j]){
                        temp[k++] = data[j++];
                }else{
                        temp[k++] = data[i++];
                }
        }
        while(i <= middle){
                temp[k++] = data[i++];
        }
        while(j <= end){
                temp[k++] = data[j++];
        }
        for(i = start; i <= end; i++){ //直接用memcpy也是可以的
                data[i] = temp[i];
        }
}
//先分组,直至每组只有两个元素再合并
int merge_sort(int* data, int *temp, int start, int end){
        int middle;
        if (start < end){
                middle = start + (end - start) / 2; //分割完后，只有2个元素
                merge_sort(data, temp, start, middle);
                merge_sort(data, temp, middle + 1, end);
                sort(data, temp, start, middle, end);
        }
        return 0;
}

int sort(int *data, int left, int right){
        if(right < left) return -1;
        int i = left;
        int j = right;
        int key = data[left];
        while(i != j){
                while(i < j && key <= data[j]){
                        j--;
                }
                data[i] = data[j];
                while(i < j && key >= data[i]){
                        i++;
                }
                data[j] = data[i];
        }
        data[i] = key;
        sort(data, left, i-1);
        sort(data, i+1, right);
        return 0;
}
int quick_sort(int *data, int length)
{
        sort(data, 0, length -1);
        return 0;
}