快速排序算法实现

快速排序算法实现
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说快速排序算法实现,希望能够帮助大家进步!!!

/*

快速排序算法的基本思想是,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

一趟快速排序的算法是:附设两个指针low和high,它们的初值分别为low和high,设枢轴记录的关键字为pivotkey,则首先从 high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换,
然后从low所指位置起向后搜索,找到第一个关键字大于 pivotkey的记录和枢轴记录互相交换,重复这两步直至low=high为止。由此可以该“枢轴”记录最后所落的位置i作为分界线,将序列分隔成两个子序列。

实际上low和high可以被理解为位置标志,它们所指向的只是位置。而pivotkey就是一个数值,它被选取被序列中的一个特定元素。在每趟的快排当中,都是low和high所指位置的元素和pivotkey来做比较。

*/


//
打印数组


void
 PrintArray(
int
  array[] , 
int
 n)
{

    
int
 i;
    

for
(i
=
0
;i
<
n;i
++
)
        printf(

"
 %d 
"
,array[i]);
    printf(

"
\n
"
);

}

int
 Partition(
int
 array[],
int
 low, 
int
 high)
{

    
int
 pivot 
=
 array[low];
    

while
 (low 
<
 high)
    {

        

while
 (low 
<
 high 
&&
 array[high] 
>=
 pivot) 
--
high;
        array[low] 

=
 array[high];
        

while
 (low 
<
 high 
&&
 array[low] 
<=
 pivot) 
++
low;
        array[high] 

=
 array[low];
    }
    array[low] 

=
 pivot;
    

return
 low;
}


void
 QuickSort(
int
 array[],
int
 low,
int
 high)
{

    

if
 (low 
<
 high)
    {

        

int
 pivotkey 
=
 Partition(array,low, high);
        QuickSort(array,low, pivotkey 

-
 
1
);
        QuickSort(array,pivotkey 

+
 
1
, high);
    }   
}


void
 TestQuickSort()
{

    

int
 array[
8

=
{

38
,
20
,
46
,
38
,
74
,
91
,
12
,
25
};
    QuickSort(array,

0
,
7
);
    PrintArray(array,

8
);
}

转载于:https://www.cnblogs.com/hb_cattle/archive/2009/08/23/1552476.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29659

发表评论