广州越秀网站建设公司,东莞网站开发前三强,如何设计网店店面,嘉兴网站关键字优化快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想为∶任取待排序元素序列中的某元素作为基准值#xff0c;按照该排序码将待排序集合分割成两子序列#xff0c;左子序列中所有元素均小于基准值#xff0c;右子序列中所有元素均大于基准值#xff0c;… 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想为∶任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
void QuickSort(int array[], int left, int right)
{if(right - left 1)return; int div partion(array, left, right);QuickSort(array, left, div); QuickSort(array, div1, right);
} 上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有: 1.hoare版本 2.挖坑法 3.前后指针版本
下面将介绍三种方法在此之前我们现需写一个三数取中代码
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]) {return left;}else{return right;}}else {if (a[mid] a[right]){return mid;}else if (a[left] a[right]) {return left;}else{return right;}}
} 一、hoare版本 具体步骤
先选取数组左边的第一个数作为key定义一个左下标left指向最左边的数定义一个右下标right指向最右边的数。然后让right先往左遍历找到第一个比key大的值让left后向右遍历找到第一个比key小的值。这时左边的值都比key小右边的值都比key大交换left和right指向的值。这样一趟排序就结束了key就在了它应该在的位置上。重复以上步骤直到整个序列有序。
核心代码
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){while (left right a[right] a[keyi]){--right;}while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestQuickSort()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}
实验结果 二、挖坑法 具体步骤 首先设置两个指针一个指向数组的起始位置一个指向数组的末尾位置。从末尾位置开始向前遍历找到第一个小于基准元素的元素并将其填入起始位置的坑中。然后从起始位置开始向后遍历找到第一个大于基准元素的元素并将其填入上一步所挖的坑中。重复上述步骤直到起始位置和末尾位置相遇。此时将基准元素填入最后一个坑中这样就完成了一次分区操作。最后对分区后的左右两个子数组分别递归地进行上述步骤。
核心代码
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];int hole left;while (left right){while (left right a[right] key){--right;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestQuickSort()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}
实验结果 三、前后指针版本 具体步骤 选择枢轴元素在数组中选择一个元素作为枢轴一般选择第一个元素或最后一个元素。 初始化左右指针左指针指向数组的第一个元素右指针指向数组的最后一个元素。 划分过程从前往后遍历数组当找到一个比枢轴大的元素时将左指针向右移动一位从后往前遍历数组当找到一个比枢轴小的元素时将右指针向左移动一位。当左指针大于等于右指针时说明已经找到正确的位置将枢轴与左指针所在位置的元素交换。 递归处理将枢轴左边的部分作为新的子数组递归调用快速排序函数将枢轴右边的部分作为新的子数组递归调用快速排序函数。
核心代码
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestQuickSort()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestQuickSort();return 0;
}
实验结果 四、非递归版本 快速排序的非递归版本是递归版本的一种优化主要是通过将递归过程转化为循环来实现。基本思路是将数组分为两部分一部分比基准值小另一部分比基准值大然后对这两部分分别进行快速排序。这个过程可以通过循环来实现而不是通过递归调用函数自身。
具体步骤 首先从数组中挑选一个元素作为基准值然后将所有小于基准值的元素移动到基准值的左边将所有大于基准值的元素移动到基准值的右边。接下来对基准值左右两边的子数组分别进行相同的操作直到数组完全有序。
核心代码
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(st);
StackPush(st, left);
StackPush(st, right);
while (StackEmpty(st) ! 0)
{right StackTop(st);StackPop(st);left StackTop(st);StackPop(st);if(right - left 1)continue;int div PartSort1(a, left, right);// 以基准值为分割点形成左右两部分[left, div) 和 [div1, right)StackPush(st, div1);StackPush(st, right);StackPush(st, left);StackPush(st, div);
}StackDestroy(s);
} 感兴趣的同学可以自行练习。 五、快速排序特性总结 1.快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2.时间复杂度:O(N*logN) 3.空间复杂度:O(logN) 4.稳定性:不稳定 结语快速排序的相关分享到这里就结束了希望对大家的学习会有帮助如果大家有什么问题或者不同的见解欢迎大家的留言~~~
