2.2.3 顺序表应用举例

2.2.3 顺序表应用举例
【例2-1】 将顺序表(a1,a2,…，an)重新排列为以 a为界的两部分：a1前面的值均比a1小，a1后面的值都比 a1大（这里假设数据元素的类型具有可比性，不妨设为整型），操作前后如图2-5所示，这一操作称为划分，a也称为基准。

思路1：快排简易版

由于只需要分成两部分，不需要整体排序，所以一次快排就可以了。

双指针，左指针遇到比a1大的值停止，右指针遇到比a1小的停止，如果左指针比右指针小就交换，时间复杂度O(n)。

void quick_sort(int q[], int l, int r，int x)
{
    int i = l - 1, j = r + 1;
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    for (int i = 1;; i++) {
        if (q[i] < x)q[i - 1] = q[i];
        else {
            q[i - 1] = x;
            break;
        }
    }
}
//顺序表：SeqList *L;
//传入参数：L->data,1,L->last,L->data[0]

思路2：

额外找两个数组，时间复杂度O(n)

void merge_sort(int q[], int l, int r, int x) {
	int a[Maxsize],b[Maxsize];
	int p1=0,p2=0;
	for (int i = l; i <= r; i++) {//比基准小放a数组，比基准大放b数组，c表示有几个和基准相等
		if (q[i] < x) a[p1++] = q[i];
		else if (q[i] > x)b[p2++] = q[i];
	}
    //按顺序放回数组
	int i = 0;
	for (; i < p1; i++) {
		q[i] = a[i];
	}
    a[i++]=x;
	for (int j=0; j < p2; j++) {
		q[i++] = b[j];
	}
}