小猿圈算法之快排

算法在面试的时候经常会遇到,是不可避免的,只要你面试,肯定得会算法,冒泡、二分这些基础的算法估计实习的时候才会被面试到,稍微高级一点的算法快排,一般是毕业生、或者换工作的朋友都会被问到,小猿圈详细描述一下快排的思想和快排的算法,大家可以看一下。

//排序--快速排序法

include<stdio.h>

include<stdlib.h>

include<string.h>

include<time.h>

/*

快速排序

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,

其中一部分的所有数据都比另外一部分的所有数据都要小

,然后再按此方法对这两部分数据分别进行快速排序,

整个排序过程可以递归进行,

以此达到整个数据变成有序序列。

快速排序:

第一步:在数据集之中,选择一个元素作为"基准"(pivot)

第二步:所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边

第三步:对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止

*/

//位置调换

void MySwap(int *arr,int a,int b){

int temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

//一轮快速排序 single

int SingleSort(int *arr, int low, int high){

//获取枢轴

int pv = arr[low];

while (low < high){

    //high向左移动

    while (low<high&&arr[high] >= pv){

        high--;

    }

    //此时 high下标的元素的值不大于枢轴  可以调换位置

    MySwap(arr, low, high);

    //注意 此时枢轴的位置在high上  high的值就是Pv

    //low向右移动

    while (low<high&&arr[low]< pv){

        low++;

    }

    //此时 low下标的元素的值大于枢轴  可以调换位置

    MySwap(arr, low, high);

    //注意 此时枢轴的位置在low上  low的值就是Pv

}

//返回最终pv所在的位置  此时必定 low==high

return low;

}

//快速排序

void QuickSort(int *arr, int low, int high){

if (low >= high)

{

    return;

}

//排序一轮

int pivot = SingleSort(arr, low, high);

//排序产生的左数组

QuickSort(arr, low, pivot - 1);

//排序产生的右数组

QuickSort(arr, pivot + 1, high);

}

//打印数组

void Print(int * arr, int num){

if (arr == NULL)

{

    printf("传入参数不可以为空!\n");

    return;

}

int i = 0;

for (int i = 0; i < num; i++)

{

    printf("%5d", *(arr + i));

}

printf("\n");

}

void Test(){

int i = 0;

int arr[10] = { 0 };

//定义时间类型变量

time_t ts;

//生成随机数种子

srand((unsigned int)time(&ts));

for (i = 0; i < 10; i++)

{

    arr[i] = (int)(rand() % 100);

}

//打印数组

printf("\n原始数据----\n");

Print(arr, 10);

//快速排序

printf("快速排序之后的数据\n");

QuickSort(arr, 0,9);

Print(arr, 10);

}

void main(){

Test();

system("pause");

}

大家学会了吗?首先一定要把快排的思想理解透彻,只有思想透彻了,代码才会很顺手敲出来,要不虽然代码懂了,估计过两天就忘了,所以思想很重要,想要了解其他算法,可以去小猿圈学一下,全都是免费的视频资料,希望大家真的能学到!

评论

暂无评论