电竞网站方案设计,做门户网站用什么系统,网站建设助您购选,c 做网站快速排序的基本思想是#xff1a; 通过一趟排序将待排的记录划分为独立的两部分#xff0c;称为前半区和后半区#xff0c;其中#xff0c;前半区中记录的关键字均不大于后半区记录的关键字#xff0c;然后再分别对这两部分记录继续进行快速排序#xff0c;从而使整个序列… 快速排序的基本思想是 通过一趟排序将待排的记录划分为独立的两部分称为前半区和后半区其中前半区中记录的关键字均不大于后半区记录的关键字然后再分别对这两部分记录继续进行快速排序从而使整个序列有序。 一趟快速排序的过程称为一次划分具体做法是附设两个位置指示变量i 和j它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录(通常是第一个记录)的关键字为pivot则首先从 j 所指位置起向前搜索找到第一个关键字小于 pivot 的记录时将该记录向前移到 i 指示的位置然后从i 所指位置起向后搜索找到第一个关键字大于 pivot 的记录时将该记录向后移到 j 所指位置重复该过程直至 i 与 j 相等为止。 【函数】快速排序过程中的划分。
int partition(int data[], int low, int high)
/*用data[low]作为枢轴元素 pivot 进行划分*/
/*使得 data[low..i-l]均不大于 pivotdata[il..high]均不小于 pivot*)
{int i, j;int pivot;pivot data[low]; ilow; jhigh;while(i j){ /*从数组的两端交替地向中间扫描*/while(i j data[j] pivot) j--;data[i] data[j]; /*比枢轴元素小者往前移*/while (i j data[i] pivot) i;data[j] data[i]; /*比枢轴元素大者向后移*/}data[i] pivot;return i;
}【函数】用快速排序方法对整型数组进行非递减排序。
void quickSort(int data[], int low, int high)
/*用快速排序方法对数组元素 data[low..high]作非递减排序*
{if(low high){int loc partition(data, low, high); /*进行划分*/quicksort(data, low, loc-1): /*对前半区进行快速排序*/quicksort(data, loc1, high); /*对后半区进行快速排序*/}
}/* quickSort */快速排序算法的时间复杂度为 O(nlog2n)在所有算法复杂度为此数量级的排序方法中快速排序被认为是平均性能最好的一种。但是若初始记录序列按关键字有序或基本有序时即每次划分都是将序列划分为某一半序列的长度为0 的情况此时快速排序的性能退化为时间复杂度是 O(n2)。快速排序是不稳定的排序方法。
