分治法之快速排序

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;
}