快速排序

49 38 65 97 76 13 27——————49原始

27 38 65 97 76 13 49——————49   1次

27 38 49 97 76 13 65——————49   2次

27 38 13 97 76 49 65——————49   3次

27 38 13 49 76 97 65——————49   4次

一趟快速排序

 

排序1：

#include iostream #include time.h #define ARYSIZE 100000 using namespace std; void QuickSort(int ary[], int nBegin, int nEnd) int tKey = ary[nBegin]; int tLeft = nBegin; int tRight = nEnd;//以第一个数为参照做比较 if(tLeft = tRight) return; while(tLeft tRight) while(tLeft tRight ary[tRight] = tKey) tRight--; ary[tLeft] = ary[tRight]; while(tLeft tRight ary[tLeft] = tKey) tLeft++; ary[tRight] = ary[tLeft]; ary[tRight] = tKey; QuickSort(ary, nBegin, tRight-1); QuickSort(ary, tRight+1, nEnd);//递归 int main(int argc, char *argv[]) int ary[ARYSIZE] = {0}; srand((unsigned int)time(NULL)); for (int i = 0; i ARYSIZE; ++i) ary[i] = rand() % 100; QuickSort(ary, 0, ARYSIZE - 1); getchar(); }

排序1比较块；

 

排序2：

#include iostream #include time.h #define ARYSIZE 100000 using namespace std; void swap(int *a, int *b) int t=*a; *a=*b; *b=t; void QuickSort(int arr[], int beg, int end) if (end = beg + 1) int piv = arr[beg], k = beg + 1, r = end; while (k r) if (arr[k] piv) k++; else swap( arr[k], arr[r--]); if (arr[k] piv) swap( arr[k], arr[beg]); QuickSort(arr, beg, k); QuickSort(arr, r, end); else if (end - beg == 1) return; swap( arr[--k], arr[beg]); QuickSort(arr, beg, k); QuickSort(arr, r, end); int main(int argc, char *argv[]) int ary[ARYSIZE] = {0}; srand((unsigned int)time(NULL)); for (int i = 0; i ARYSIZE; ++i) ary[i] = rand() % 100; QuickSort(ary, 0, ARYSIZE - 1); getchar();

快速排序 概念：快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
【1. 快速排序】 1. 确定分界点：q[l] , q[(1 + r)/2] , q[r] , 随机 2. 调整区间的范围：使得在`分界点左侧是数都 = x`, `分界点右侧的数都 = x `(`重点处理`)
快速排序就这么简单 从前面已经讲解了冒泡排序、选择排序、插入排序了，本章主要讲解的是快速排序，希望大家看完能够理解并手写出快速排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。
快速排序（C++实现） 一、快速排序的基本实现 快速排序算法是一种基于交换的高效的排序算法，它采用了分治法的思想： 1、从数列中取出一个数作为基准数（枢轴，pivot）。 2、将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。 3、再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。 快排最重要的一步就是划分了。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。
快速排序实现 算法思想：快速排序时这样的一种排序，选取数组中的第一个元素arr[0]作为依据，遍历一遍数组后，使得数组中的第一个元素进入正确的位置，即在该位置左面的元素均小于等于arr[0]，在该位置右面的元素均大于等于arr[0]。