C言语疾速排序算法及代码

疾速排序是对冒泡法排序的一种改良。
疾速排序算法 的根本思惟是：将所要停止排序的数分为阁下两个局部，个中一局部的一切数据都比别的一 局部的数据小，然后将所分得的两局部数据停止异样的划分，反复履行以上的划分操作，直 到一切要停止排序的数据变为有序为止。
能够仅依据根本思惟对疾速排序的看法并不深，接下来以对n个无序数列A[0], A[1]…, A[n-1]采取疾速排序办法停止升序陈列为例停止解说。
(1)界说两个变量low和high，将low、high辨别设置为要停止排序的序列的肇端元素和最初一个元素的下标。第一次，low和high的取值辨别为0和n-1，接下来的每次取值由划分失掉的序列肇端元素和最初一个元素的下标来决议。
(2)界说一个变量key，接下来以key的取值为基准将数组A划分为阁下两个局部，通 常，key值为要停止排序序列的第一个元素值。第一次的取值为A[0]，今后毎次取值由要划 分序列的肇端元素决议。
(3)从high所指向的数组元素开端向左扫描，扫描的同时将下标为high的数组元素顺次与划分基准值key停止比拟操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个地位。
(4)假如low仍然小于high，那么由low所指向的数组元素开端向右扫描，扫描的同时将下标为low的数组元素值顺次与划分的基准值key停止比拟操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个地位。
(5)反复步调(3) (4)，直到low的植不小于high为止，这时胜利划分后失掉的阁下两局部辨别为A[low……pos-1]和A[pos+1……high]，个中，pos下标所对应的数组元素的值就是停止划分的基准值key，所以在划分完毕时还要将下标为pos的数组元素赋值 为 key。
(6)将划分失掉的阁下两局部A[low……pos-1]和A[pos+1……high]持续采取以上操作步调停止划分，直到失掉有序序列为止。
为了可以加深读者的了解，接下来经过一段代码来理解疾速排序的详细完成办法。

			#include <stdio.h> #include <stdlib.h> #define N 6 int partition(int arr[], int low, int high){ int key; key = arr[low]; while(low<high){ while(low <high && arr[high]>= key ) high--; if(low<high) arr[low++] = arr[high]; while( low<high && arr[low]<=key ) low++; if(low<high) arr[high--] = arr[low]; } arr[low] = key; return low; } void quick_sort(int arr[], int start, int end){ int pos; if (start<end){ pos = partition(arr, start, end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } return; } int main(void){ int i; int arr[N]={32,12,7, 78, 23,45}; printf("排序前 \n"); for(i=0;i<N;i++) printf("%d\t",arr[i]); quick_sort(arr,0,N-1); printf("\n 排序后 \n"); for(i=0; i<N; i++) printf("%d\t", arr[i]); printf ("\n"); system("pause"); return 0; }

运转后果：

排序前
32    12    7    78    23    45
排序后
7    12    23    32    45    78

在下面的代码中，依据后面引见的步调一步步完成了疾速排序算法。接下来经过表示图来演示第一次划分操作。
在第一次划分操作中，先辈行初始设置，key的值是停止划分的基准，其值为要划分数 组的第一个元素值，在下面的排序序列中为第一个元素值32，同时将low设置为要排序数组中第一个元素的下标，第一次排序操作时其值为0，将high设置为要排序序列最初一个 元素的下标，在下面的排序序列中其第一次取值为5。先将下标为high的数组元素与key停止比拟，因为该元素值大于key，因而high向左挪动一个地位持续扫描。因为接下来的值为 23，小于key的值，因而将23赋值给下标为low所指向的数组元素。接下来将low右移一 个地位，将low所指向的数组元素的值与key停止比拟，由干接下来的12、7都小于key， 因而low持续右移扫描，直至下标low所指向的数组元素的值为78即大于key为止，将78赋值给下标为high所指向的数组元素，同时将high左移一个地位。接下因由于low不再小于high，划分完毕。需求留意的是，在停止划分的进程中，多是将扫描的值与key的值停止比照，假如小于key，那么将该值赋值给数组中的别的一个元素，而该元素的值并没有改动。 从图中可以看出这一点，所以需求在划分的最初将作为划分基准的key值赋值给下标为 pos的数组元素，这个元素不再介入接下来的划分操作。

第一次划分操作

第一轮划分完毕后，失掉了阁下两局部序列A[0]、A[1]、A[2]和A[4]、A[5]，持续进 行划分，即对毎轮划分后失掉的两局部序列持续划分，直至失掉有序序列为止。