Question

谁能详细讲解下c语言中的快速排序

若以下回答无法解决问题，邀请你更新回答

Answer 1

（1）直接插入排序
直接插入排序类似于玩纸牌时整理手中纸牌的过程，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好。

（2）希尔排序
先将整个待排序列分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序时，再对整个记录进行一次直接插入排序。
在本程序的希尔排序中，希尔“逐段分割”的“增量”的计算方法使用：d=d/3+1;d的初始值为n，即数组长度。

（3）冒泡排序
两两比较相邻记录的关键码，如果凡序则交换，直到没有反序记录为止。
具体排序过程为：
1. 将整个待排序的记录划分为有序区和无序区，初始状态有序区为空，无序区包所所有待排记录；
2. 对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移动，大大记录向后移动；
3. 重复执行2，直到无序区中没有反序的记录。

（4）快速排序
在快速排序中，记录的比较和移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面直接移动到前面，记录移动距离较远，从而减少了总的移动次数。快速排序的伪代码如下：
1. 将i和j分别指向待排序区域的最左和最右侧记录的位置；
2. 重复下述过程，知道i=j
a) 右侧扫描，直到记录j的关键码小于基准记录的关键码；
b) 如果i<j，则将r[j]与r[i]交换，并将i++；
c) 左侧扫描，知道记录i的关键码大于基准记录的关键码；
d) 如果i<j，则将r[i]与r[j]交换，并将i++；
3. 退出循环，说明i和j指向了基准记录所在位置，返回该位置。

（5）直接选择排序
直接选择排序的实现过程：
1． 将整个记录序列划分为有序区和无序区，初始状态有序区为空，无序区含有待排序所有记录；
2． 在无序区中选取关键码最小的记录，将它与无序区中的第一个记录交换，使得有序去扩展一个记录，而无序区减少一个记录；
3． 不断重复2，知道无序区只剩下一个记录为止。

（6）堆排序
堆排序是直接选择排序的一种改进，改进着眼于如何减少关键码的比较次数。
堆（heap）是具有下列性质的完全二叉树：每个节点的值都小于或者等于其左右孩子的值（小根堆）；或者每个节点的值都大于或等于其左右孩子节点的值（大根堆）。
本次算法，我们采用大根堆排序。先将原数组堆化，然后再进行排序，排序方法入下图所示：

图1

（7）归并排序
本次算法中，用递归实现二路归并。先将待排序列的记录序列分为两个相等的子序列，并分别将这两个子序列用归并的方法进行排序，然后调试一次归并算法Merge，再将这两个有序子序列合并成一个含有全部记录的有序序列。
1）快速排序和堆排序源程序
////////////////////////////////////快速排序
void quick_sort( int *a, int low, int high)
{
int i = low, j = high;
int temp = a[ low];
if( low >= high) return;
while( i != j)
{
while( i < j && a[ j] >= temp)
j--;
a[ i] = a[ j];
while( i < j && a[ i] <= temp)
i++;
a[ j] = a[ i];
}
a[ i] = temp;
quick_sort( a, low, i - 1); //递归
quick_sort( a, i + 1, high);
}

////////////////////////////////////堆排序
void MaxHeapify( int *a, int i, int n) //此处i重开始，因此一下所有相关下标-1
{
int lc = i*2-1, rc = i*2;
int largest; //largest，最大数下标
int temp;
if( lc < n && a[ lc] > a [ i-1])
{
largest = lc;
} else{
largest = i-1;
}
if( rc < n && a[ rc] > a[largest])
{
largest = rc;
}
if( largest != i-1)
{
temp = a[ i-1];
a[ i-1] = a[ largest];
a[ largest] = temp;
largest++; //恢复i值，即i+1
MaxHeapify( a, largest, n);
}
}
void BuildMaxHeap( int *a, int n)
{
for( int i = n/2; i > 0; i--)
{

MaxHeapify( a, i, n);
}
}
void heap_sort( int *a, int n)
{
int i, temp;
BuildMaxHeap( a, n);
for( i = n-1; i > 0 ; i--)
{
temp = a[ 0];
a[ 0] = a[ i];
a[ i] = temp;
MaxHeapify( a, 1, i); //将a[0] 下沉
}
}