深圳java培训机构

鲲鹏IT培训

参考价格：电话咨询

咨询电话： 400-656-3385

立即预约确认报名

姓名3：

电话：

城市：

想学
什么：

课程说明

课程级别

入门级

培训周期

半年内

上课地址

罗湖区宝安南路嘉宾花园A座4楼

【课程详情】

排序（Quick Sort）：
排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序的目的。
例题：假设现在我们要对数组{50, 10, 90, 30, 70, 40, 80, 60, 20}进行排序。算法实现如下：
#include
using namespace std;
int Partion(int *array, int start, int end)
{
/* 判断参数合法性 */
if (array == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 取枢纽为个元素，则将array[start,end]以枢纽分成两部分，
前部分小于pivotKey,后部分大于pivotKey */
int pivotKey = array[start];
int i = start, j = end;
while (i < j)
{
while (i < j && array[j] >= pivotKey)
{
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivotKey)
{
i++;
}
array[j] = array[i];
}
array[i] = pivotKey;
return i;
}
void QuickSort(int *array, int start, int end)
{
/* 判断参数合法性 */
if (array == NULL || start < 0 || end < 0 || start > end)
{
return;
}
if (start < end)
{
int pivot = Partion(array, start, end);
QuickSort(array, start, pivot - 1);
QuickSort(array, pivot + 1, end);
}
}
int main()
{
int array[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
QuickSort(array, 0, 8);
for (int i = 0; i < 8; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
#include
using namespace std;
int Partion(int *array, int start, int end)
{
/* 判断参数合法性 */
if (array == NULL || start < 0 || end < 0 || start > end)
{
return -1;
}
/* 取枢纽为个元素，则将array[start,end]以枢纽分成两部分，
前部分小于pivotKey,后部分大于pivotKey */
int pivotKey = array[start];
int i = start, j = end;
while (i < j)
{
while (i < j && array[j] >= pivotKey)
{
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivotKey)
{
i++;
}
array[j] = array[i];
}
array[i] = pivotKey;
return i;
}
void QuickSort(int *array, int start, int end)
{
/* 判断参数合法性 */
if (array == NULL || start < 0 || end < 0 || start > end)
{
return;
}
if (start < end)
{
int pivot = Partion(array, start, end);
QuickSort(array, start, pivot - 1);
QuickSort(array, pivot + 1, end);
}
}
int main()
{
int array[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
QuickSort(array, 0, 8);
for (int i = 0; i < 8; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
下面我们考虑，如果使用排序的基本思想来解决以下问题。
例1：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。（剑指offer，面试题29，页数：163）
如果数组中有一个数字出现的次数超过数组长度的一半，则如果将该数组排序之后，那么其array[length / 2]中的值必是该值。同样，该值是整个数组的中位数。即长度为n的数组的第n/2大的数字。
考虑排序算法，我们先在数组中选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个被选中的数字的下标刚好是n/2，则这个数字就是数组的中位数。