文章目录
快速排序实现思路实现代码快速排序
快速排序是将等待排序的集合分成两部分，设定一个k值，其中一部分小于这个k值，另外一部分大于这个k值。对每个部分重复这个过程。知道每部分都只有一个元素的时候。就可以完成排序了。
实现思路
首先我们需要选取一个k值， 一般情况下我们可以使用数组的第一个值或者最后一个值。
假设我们先选取数组的第一位为k值。 我们假设为6。
然后我们利用两个指针，一个指针(left)从左边开始向右移动，一个指针(right)从右边开始向左移动,当left指针找到一个大于k值时停下，当right指针找到一个小于k值时停下。 然后交换两个指针指向的值，之后再各自移动。当两指针相遇时停下。然后将所在位置的值与k值，即数组的第一个位置交换。
需要注意的是，当我们使用这样的方法交换元素时，如果我们我们的k值选择的是数组的第一个位置，则在移动时，我们需要先移动right指针，再移动left指针，这样才能确保我们最后指针在相遇时， 是一个小于k的元素所在的位置，这样在和k值交换后才能保证数组前部分的所有元素都是小于k的，后半部分都是大于k的。
同理，如果我们的k值选择的是数组末的位置，则在移动时，需要先移动left指针，再移动right指针，以确保最后指针相遇在一个大于k值的元素所在的位置。
这样， 我们第一趟排序就完成了。然后整个数组以k为分解分成了两部分，我们只需要对这两部分都在进行这样的操作，递归调用。最终就可以完成排序。
快速排序的时间复杂度是不稳定的，因为我们一直将数组分段，如果我们每次都恰好将元素分成相等的两部分，这时候我们可以得到最好的结果。即时间复杂度为O(nlogn)。可如果我们每次都恰好选到了数组中最大或最小的元素。那我们就会得到最差的结果，即时间复杂度为O(n²)。
实现代码
所以我们在实现代码时，为了避免我们遇到“每次选择的k值都恰好是最大或者最小的数”这种情况。我们加入了“三数取中”的部分。即每次选取k时， 我们从数组的第一个元素 ， 最后一个元素，中间的元素三个元素中选择大小中间的值为k。具体代码为：
int* QuickSort(DATATYPE* data, int left, int right){if (left >= right)return data;int mid = (left + right) / 2;// 三数取中if ((data[left] <= data[right] && data[right] <= data[mid])|| (data[mid] <= data[right] && data[right] <= data[left]))Swap(&data[left], &data[right]);else if ((data[left] <= data[mid] && data[mid] <= data[right])|| (data[right] <= data[mid] && data[mid] <= data[left]))Swap(&data[mid], &data[left]);// 三数取中int tmp = data[left];int nleft = left;int nright = right;while (left < right){while (data[right] >= tmp && left < right)right--;while (data[left] <= tmp && left < right)left++;if (left < right)Swap(&data[left],&data[right]);}Swap(&data[nleft], &data[left]);QuickSort(data, nleft, left - 1);QuickSort(data, right + 1, nright);return data; }
