三合一建站网站,郑州哪里做网站,外国网站在内地做seo,莱州市双语网站大家好#xff0c;我是怒码少年小码。
快速排序
选取pivot中心轴将大于pivot中心轴的元素放在中心轴的右边将小于pivot中心轴的元素放在中心轴的左边重复上述过程
实现方式一#xff1a;
void quickSort(int arr[], int left, int right) {if (left right) {int pi…大家好我是怒码少年小码。
快速排序
选取pivot中心轴将大于pivot中心轴的元素放在中心轴的右边将小于pivot中心轴的元素放在中心轴的左边重复上述过程
实现方式一
void quickSort(int arr[], int left, int right) {if (left right) {int pivot arr[right];int i left - 1;for (int j left; j right; j) {if (arr[j] pivot) {i;int temp arr[i];arr[i] arr[j];arr[j] temp;}}//哨兵移动到位置pivotIndex上int pivotIndex i 1 ;int temp arr[pivotIndex];arr[pivotIndex] arr[right];arr[right] temp;quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex 1, right);}//输出查看for (int i 0; i right 1; i) {cout arr[i] ,;}cout endl;
}看到这么多的代码是不是怕了呀不怕我们一起看。
这段代码中我们把pivot保存数组中最右边的元素为基准。定义一个变量i保存需要交换元素的前一个元素。定义一个变量j从左至右遍历数组判断是否需要交换。最后再用递归实现一直重复的过程。
实现方式二
下面这种方式就更好理解了取中间结点为pivotleft和right用于遍历和比较当满足left right 并且要找到不符合条件的元素后就停下来执行交换。可以输出打印检查看看对不对。最后再递归地重复这个过程。
void quickSort01(int arr[], int start, int end) {if (start end) {return;}int left start, right end;int pivot arr[(start end) / 2];while (left right) {while (left right arr[left] pivot) {left;}while (left right arr[right] pivot) {right--;}if (left right) {int temp arr[left];arr[left] arr[right];arr[right] temp;left;right--;}}for (int i 0; i right 1; i) {cout arr[i] ,;}cout endl;quickSort(arr, start, right);quickSort(arr, left, end);
}
