快速排序算法c语言指针,【超详细】一文弄懂快速排序算法（附快速排序、冒泡排序代码）...

快速排序，是一种既不浪费空间，算法执行效率又快速的“折中”排序算法，适用于顺序很乱、很长的数字序列，

一、快速排序的算法原理

每次都取数组的第一个元素作为基准元素，凡是大于基准元素的都放在它的右边，凡是小于基准元素的都放在它的左边，具体步骤如下：

第一轮排序：

1、令第一个元素为基准元素，并设置两个变量i和j(也称为哨兵i、哨兵j)， i在序列的最左端，j在序列的最右端。(i = left；j = right)

2、j 从右往左试探，直到 j 找到小于基准元素值的元素就停止先； i 从左往右试探，直到 i 找到大于基准元素值的元素就停止。当 i 和 j 都停止了后，交换 i 和 j 所指向的元素。交换后， j 、 i 按以上步骤继续试探。

3、直到 i 和 j 相遇之后，则i的值与基准元素交换，第一轮排序结束。

第一轮排序结束后，分别对基准元素左右两边的序列重复以上步骤。

二、快速排序示例及其示意图

快速排序算法示意图

三、快速排序代码、冒泡排序代码

QuickSort.c 快速排序

#include

#include

void QuickSort(int *Array, int left, int right); //快速排序

int main(int argc, char const *argv[])

{

int ARRAY_SIZE = 0;

int *array;

int i;

//输入要排序数组的长度，并为指针变量 array 动态分配内存

printf("请输入要排序的数组长度：");

scanf("%d", &ARRAY_SIZE);

array = (int *)malloc(ARRAY_SIZE*sizeof(int));

//输入要排序数组的各个元素的值

printf("请输入%d个数组元素(以空格隔开)：n", ARRAY_SIZE);

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

{

scanf("%d", &array[i]);

}

printf("n");

/**快速排序**/

QuickSort(array, 0, ARRAY_SIZE-1);

//输出排序后的数组元素值

printf("排序后的数组为：");

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

{

printf("%d ", array[i]);

}

printf("(从小到大)n");

return 0;

}

//快速排序

void QuickSort(int *Array, int left, int right)

{

int pivot;

int i, j;

int swap_tmp;

if(left > right)

return ;

pivot = Array[left];

i = left;

j = right;

while(i != j)

{

while((Array[j] >= pivot) && (i < j))

j--;

while((Array[i] <= pivot) && (i < j))

i++;

if(i < j)

{

swap_tmp = Array[i];

Array[i] = Array[j];

Array[j] = swap_tmp;

}

}

//pivot = Array[left];

Array[left] = Array[i]; //原基准元素 与 Array[i]或Array[j] 交换值

Array[i] = pivot;

//第一轮快速排序已结束

QuickSort(Array, left, i-1); //左边序列排序

QuickSort(Array, i+1, right); //右边序列排序

}

快速排序

BubbleSort.c 冒泡排序

#include

#include

void BublleSort(int *Array, int ArraySize); //冒泡排序

int main(int argc, char const *argv[])

{

int ARRAY_SIZE = 0;

int *array;

int i;

//输入要排序数组的长度，并为指针变量 array 动态分配内存

printf("请输入要排序的数组长度：");

scanf("%d", &ARRAY_SIZE);

array = (int *)malloc(ARRAY_SIZE*sizeof(int));

//输入要排序数组的各个元素的值

printf("请输入%d个数组元素(以空格隔开)：n", ARRAY_SIZE);

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

{

scanf("%d", &array[i]);

}

printf("n");

/**冒泡排序**/

BublleSort(array, ARRAY_SIZE);

//输出排序后的数组元素值

printf("排序后的数组为：");

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

{

printf("%d ", array[i]);

}

printf("(从小到大)n");

return 0;

}

//冒泡排序

void BublleSort(int *Array, int ArraySize)

{

int i, j;

int tmp;

for(i = 0; i < (ArraySize-1); i++)

{

for (j = i + 1; j < ArraySize; j++)

{

if(Array[i] > Array[j])

{

tmp = Array[i];

Array[i] = Array[j];

Array[j] = tmp;

}

}

}

}

冒泡排序