我要招人

去企业版

首页 > 试题广场 >

设有一组初始关键字序列（46,79,56,38,40,84）

[问答题]

设有一组初始关键字序列（46,79,56,38,40,84），执行第一趟快速排序后所得序列是（）

评估未通过

int partition(int a[], int left, int right){
	int pivot = a[left];
	while(left < right){
		while(left < right && a[right] >= pivot) --right;	
		a[left] = a[right];
		while(left < right && a[left] <= pivot) ++left;
		a[right] = a[left];
	}
	a[left] = pivot;
	return left;
}
//partition函数通常把第一位作为pivot，对剩下的元素用前后指针来调整位置，最终将pivot归位
//最终结果为40 38 46 56 79 84

编辑于 2017-04-22 21:18:51 回复(0)

更多回答

牛客8940652号

//结果应为40 38 46 56 79 84
void quickSort（SortObject *pvector,int head,int tail）
{
    int i,j;
    RecordNode temp,*data=pvector->record;
    if(head >= tail)return;
    i=head;j=tail;temp=data[i];
    while(i!=j)
    {
         while(i<j && data[j].key >= temp.key)
             j--;
        if(i < j)
            data[i++] = data[j]; 
        while(i<j && data[j].key <= temp.key)
            i++;
        if(i<j)
            data[j--] = data[i]; 
    }
    data[i] = temp;
    quickSort(pvector,head,i-1);
    quickSort(pvector,i+1,tail);
}

编辑于 2017-04-25 17:51:11 回复(0)

牛客882122502号

第一轮排序结果为

460,38,46,56,79,84

快速排序通常取第一个数作为基准。

算法：

void QuickSort(vector<int>& R, int start, int tail)
{
    if (start >= tail)  return;
    int i = start, j = tail;
    int tmp = R[i];
    while (i < j)
    {
        while (j > i && R[j]>=tmp)
        {
            j--;
        }
        R[i] = R[j];
        while (i < j && R[i]<=tmp)
        {
            i++;
        }
        R[j] = R[i];
    }
    //此时的i和j是相等的
    R[i] = tmp;
    showres(R);
    QuickSort(R, start, i-1);
    QuickSort(R, i+1, tail);
}

运算结果为：

快速排序的最好时间复杂度为O(nlog₂n)，最坏时间复杂度为O(n²)，平均时间复杂度为O(nlog₂n)。

最好空间复杂度为均匀地分割成两个长度接近的子区间，递归树高度为O(log₂n)，所需栈空间为O(log₂n)；最坏情况下递归树高度为O(n)，所需栈空间为O(n)。平均情况下所需递归树高度为O(log₂n)，空间复杂度为O((log₂n).

快速排序还是一种不稳定的排序方***改变元素的相对位置。

编辑于 2021-04-02 19:35:29 回复(0)

幻想舞蛇

第一次交换经历：

46,79,56,38,40,84

--------------

40,79,56,38,46,84
40,46,56,38,79,84
40,38,56,46,79,84
40,38,46,56,79,84

--------------

结果： 40,38,46,56,79,84

发表于 2019-10-11 16:32:41 回复(0)

Pancras__

40 38 46 56 79 84

发表于 2017-04-22 19:51:06 回复(0)

-顾我心-安-an

40 38 46 56 79 84

发表于 2017-04-22 14:46:56 回复(0)

提交观点

问题信息

排序

上传者：城市里的养猫者

难度：

6条回答 5收藏 3905浏览

设有一组初始关键字序列（46,79,56,38,40,84）

问题信息

热门推荐

相关试题