东北大学数据结构第八周（排序）-创新互联

7-1 快速排序
作者 朱允刚
单位 吉林大学

成都创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于成都网站建设、做网站、任城网络推广、微信小程序定制开发、任城网络营销、任城企业策划、任城品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；成都创新互联公司为所有大学生创业者提供任城建站搭建服务，24小时服务热线：18980820575，官方网址：www.cdcxhl.com

给定包含n个元素的整型数组a[1],a[2],…,a[n]，利用快速排序算法对其进行递增排序，请输出排序过程，即每次Partition之后的数组。每次选择所处理的子数组的第一个元素作为基准元素。
输入格式:

输入为两行，第一行为一个整数n（1输出格式:

输出为若干行，每行依次输出Partition后的数组，每个元素后一个空格。
输入样例:

5
4 5 3 2 1

输出样例:

2 1 3 4 5
1 2 3 4 5
1 2 3 4 5

#includeusing namespace std;
int array[1005],n;
void print(){for(int i=1;i<=n;++i){cout<int mid=a;
	a=b;
	b=mid;
}
int Partition(int array[],int left,int right){int location=left;
	array[0]=array[left];
	while(leftwhile(leftarray[0]) --right;
		while(leftif(leftint position=Partition(array,left,right);
		print();
		quicksort(array,left,position-1);
		quicksort(array,position+1,right);
	}
}
int main()
{cin>>n;
	for(int i=1;i<=n;++i){cin>>array[i];
	}
	quicksort(array,1,n);
	print();
    return 0;
}

7-2 堆排序
作者 严华云
单位 湖州师范学院

对n个数，要求用堆排序（大堆）对其进行排序。
输入格式:

第一行一个n（n<1000）。第二行给出n个数。
输出格式:

输出n行，每行n个数。第一行表示将n个数(将n个数看成一棵树)变成大堆后的结果，第二行表示将上次结果的根节点交换到现有节点的最后一个节点（然后将除最后一个节点的数看成一颗树），然后将该剩余节点树从新变成大堆后的结果输出（包括交换到最后的节点），依次类推。
输入样例:

6
7 1 6 4 3 5

输出样例:

7 4 6 1 3 5
6 4 5 1 3 7
5 4 3 1 6 7
4 1 3 5 6 7
3 1 4 5 6 7
1 3 4 5 6 7

#includeusing namespace std;
int n,x;
void print(vector& nums){for(int i=0;icout<& nums, int i, int len) {for (; (i<< 1) + 1<= len;) {int lson = (i<< 1) + 1;
        int rson = (i<< 1) + 2;
        int large;
        if (lson<= len && nums[lson] >nums[i]) {large = lson;
        } else {large = i;
        }
        if (rson<= len && nums[rson] >nums[large]) {large = rson;
        }
        if (large != i) {swap(nums[i], nums[large]);
            i = large;
        } else {break;
        }
    }
}
void buildMaxHeap(vector& nums, int len) {for (int i = len / 2; i >= 0; --i) {maxHeapify(nums, i, len);
    }
}
void heapSort(vector& nums) {int len = (int)nums.size() - 1;
    buildMaxHeap(nums, len);
    print(nums);
    for (int i = len; i >= 1; --i) {swap(nums[i], nums[0]);
        len -= 1;
        maxHeapify(nums, 0, len);
        print(nums);
    }
}
int main(){cin>>n;
	vectornums(n);
	for(int i=0;icin>>x;
		nums[i]=x;
	} 
	heapSort(nums);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：东北大学数据结构第八周（排序）-创新互联
本文URL：http://mswzjz.cn/article/deghoh.html