欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分治法之快速排序

程序员文章站 2022-06-03 16:53:32
...

1.分治法快排

1.1 介绍

分治法之快速排序
分治法之快速排序
分治法之快速排序
分治法之快速排序
分治法之快速排序

1.2 代码

/* 快速排序分治版本 */
/* https://blog.csdn.net/u013948010/article/details/78690467 */ 
/*选取最右那个为主元,每轮排序时,小与主元的通过交换往前放,大于主元的通过交换放后边,最后for循环结束时通过最后一次交换将主元放过来*/
#include <iostream>
using namespace std;

//数组打印


int quickSortPartition(int arr[], int left, int right) //每一轮具体操作 
{
	//最右侧元素选为主元x 
    int x=arr[right];
    
    //交换元素的角标 
    int index=left-1;
    
	for(int j=left;j<right;j++)
	{
		if(arr[j]<x)
		{
			index++;
			int temp=arr[index];
			arr[index]=arr[j];
			arr[j]=temp;	
		}
	}
	
	//交换分割点和主元,把主元放到中间
	index++;
	int temp=arr[index];
	arr[index]=arr[right];
	arr[right]=temp;
	
	//返回分割点 
	return index;
}

void quickSort(int arr[], int left, int right) //递归过程 
{
    //数组左界<右界才有意义,否则说明都已排好,直接返回即可
    if (left>=right)
        return;
    
    // 划分,返回基准点位置
    int index = quickSortPartition(arr, left, right);
    
    // 递归处理左右两部分,i处为分界点,不用管i了
    quickSort(arr, left, index - 1);
    quickSort(arr, index + 1, right);
}

void print(int arr[])
{
	for(int i=0;i<8;i++)
		cout<<arr[i]<<" ";
	cout<<endl; 
}
int main()
{
    int arr1[] = {2,8,7,1,3,5,6,4},arr2[]={6,10,13,5,8,3,2,11};
    cout<<"排序前:"<<endl;
    print(arr1);
    quickSort(arr1, 0, 7);
    cout<<"排序后:"<<endl;
    print(arr1);
    cout<<"排序前:"<<endl;
    print(arr2);
    quickSort(arr2, 0, 7);
    cout<<"排序后:"<<endl;
    print(arr2);
    return 0;
}

分治法之快速排序