果树电动剪刀价格:【排序结构2】交换排序

1、起泡排序 O(N^2)

起泡排序的过程很简单，首先将第一个关键字和第二个关键字比较，若为逆序，则将两个记录交换。然后再用第二个关键字和第三个关键字比较，以此类推，知道第n-1个关键字和第n个比较完，这样最大的关键字将被交换到第n个位置上。这个过程称做第一趟气泡排序。然后对前n-1进行第二趟气泡排序，将第二大的关键字交换到第n-1个位置上。当第n-1趟气泡排序完成之后，有序序列也就随之产生了。

1. #include
2. /**************************
3. * 起泡排序 Bubble Sort *
4. **************************/
5. class BubbleSort{
6. public:
7. static void inc_sort(int keys[],int size);
8. };
10. void BubbleSort :: inc_sort(int keys[], int size){
11. for(int i=size-1;i>=0;i--)
12. for(int j=0;j
13. if(keys[j]>keys[j+1]){
14. int temp=keys[j];
15. keys[j]=keys[j+1];
16. keys[j+1]=temp;
17. }
18. }
19. for(int k=0;k
20. cout<
21. cout<
22. }
23. //Test BubbleSort
24. void main(){
25. int raw[]={49,38,65,97,76,13,27,49};
26. int size=sizeof(raw)/sizeof(int);
27. BubbleSort::inc_sort(raw,size);
28. }

#include/************************** * 起泡排序 Bubble Sort   *  **************************/  class BubbleSort{public:static void inc_sort(int keys[],int size);};void BubbleSort :: inc_sort(int keys[], int size){for(int i=size-1;i>=0;i--)for(int j=0;jkeys[j+1]){int temp=keys[j];keys[j]=keys[j+1];keys[j+1]=temp;}}for(int k=0;k
显然，气泡排序的时间复杂度为O(N^2)，其空间复杂度为O(1) ，而且是稳定的。
2、快速排序 O(N*logN)
快速排序是对起泡排序的一种改进。它的基本思想就是：通过一趟排序将待排记录分割成独立的两个部分，其中一个部分的关键字都比另一个部分关键字小，然后可以分别再对这两个部分继续快排，已达到整个序列有序。
具体的做法是：对待排序列keys[n]确定两个指针(low=0，high=n-1)。然后取第一个关键字keys[0]作为pivotkey(枢轴)。首先从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录，并将这个记录的关键字与pivotkey交换。然后从low所指的位置向后搜索，找到第一个关键字大于pivotkey的记录，并交换。轮流重复这两个步骤直到low=high位置。这样一个过程我们叫做一次快排(又叫一次划分)。
对划分后的序列的两个部分继续分别快排，知道所有序列有序位置，整个过程就是快排。
Cpp代码 
#include 
class QuickSort{ 
private: 
//一次快排(划分) 
static int partition(int parts[],int low, int high); 
//快排 
static void quick_sort(int parts[],int low, int high); 
public: 
//递增排序 
static void inc_sort(int keys[],int size); 
}; 
int QuickSort :: partition(int parts[], int low, int high){ 
int pivotkey=parts[low]; //将第一个元素作为枢轴 
while(low
while(low=pivotkey) --high; //将比枢轴小的关键字记录移动到低端 
parts[low]=parts[high]; 
while(low
parts[high]=parts[low]; 
} 
parts[low]=pivotkey; 
return low; //返回枢轴的位置 
} 
void QuickSort :: quick_sort(int parts[],int low,int high){ 
if(low
int pivotloc=QuickSort::partition(parts,low,high); 
QuickSort::quick_sort(parts,low,pivotloc-1); 
QuickSort::quick_sort(parts,pivotloc+1,high); 
} 
} 
void QuickSort :: inc_sort(int keys[],int size){ 
QuickSort::quick_sort(keys,0,size-1); 
for(int k=0;k
cout<
cout<
} 
void main(){ 
int raw[]={49,38,65,97,76,13,27,49}; 
int size=sizeof(raw)/sizeof(int); 
QuickSort::inc_sort(raw,size); 
} 
#includeclass QuickSort{private://一次快排(划分)static int partition(int parts[],int low, int high);//快排static void quick_sort(int parts[],int low, int high);public://递增排序static void inc_sort(int keys[],int size);};int QuickSort :: partition(int parts[], int low, int high){int pivotkey=parts[low];//将第一个元素作为枢轴while(low=pivotkey) --high; //将比枢轴小的关键字记录移动到低端parts[low]=parts[high];while(low
C代码 
//快速排序非递归算法 
#include 
#include 
void quick_sort(int *pArr, int size){ 
int * beginIdxs=(int *)malloc(size * sizeof(int)); //记录待调整子序列的首地址 
int * endIdxs=(int *)malloc(size * sizeof(int));//记录待调整子序列的尾地址 
beginIdxs[0]=0; 
endIdxs[0]=size-1; 
int curIdx=0; 
while(curIdx>-1){ 
int low=beginIdxs[curIdx]; 
int high=endIdxs[curIdx]; 
int pivotkey=pArr[low]; //将第一个元素作为枢轴 
while(low
while(low
pArr[low]=pArr[high]; 
while(low=pArr[low]) ++low; 
pArr[high]=pArr[low]; 
} 
pArr[low]=pivotkey; 
int pivotidx=low; 
int begin=beginIdxs[curIdx]; 
int end=endIdxs[curIdx]; 
curIdx--; 
if(begin
beginIdxs[++curIdx]=begin; 
endIdxs[curIdx]=pivotidx-1; 
} 
if(end>pivotidx+1){ 
beginIdxs[++curIdx]=pivotidx+1; 
endIdxs[curIdx]=end; 
} 
} 
//打印结果 
for(int k=0;k
cout<
} 
} 
void main(){ 
int raw[]={49,38,65,97,76,13,27,49}; 
int size=sizeof(raw)/sizeof(int); 
quick_sort(raw,size); 
} 
//快速排序非递归算法#include#includevoid quick_sort(int *pArr, int size){int * beginIdxs=(int *)malloc(size * sizeof(int)); //记录待调整子序列的首地址int * endIdxs=(int *)malloc(size * sizeof(int));//记录待调整子序列的尾地址beginIdxs[0]=0;endIdxs[0]=size-1;int curIdx=0;while(curIdx>-1){int low=beginIdxs[curIdx];int high=endIdxs[curIdx];int pivotkey=pArr[low]; //将第一个元素作为枢轴  while(low=pArr[low]) ++low;pArr[high]=pArr[low];}pArr[low]=pivotkey;int pivotidx=low;int begin=beginIdxs[curIdx];int end=endIdxs[curIdx];curIdx--;if(beginpivotidx+1){beginIdxs[++curIdx]=pivotidx+1;endIdxs[curIdx]=end;}}//打印结果for(int k=0;k
快速排序的平均时间复杂度为O(N*logN)。但快速排序在待排关键字序列有序或基本有序的情况下，快速排序将蜕化成起泡排序，其时间复杂度降为O(N^2) 。 经验证明，在所有O(N*logN)级的此类排序算法中，快速排序是目前被认为最好的一种内部排序方法。但是快排需要一个栈空间来实现递归。若每一趟划分都能够均匀的分割成长度相接近的两个子序列，则栈的最大深度为[logN]+1。因此空间复杂度为O(logN)。快排也是不稳定的。
快速排序有一个最坏的可能性，因此也就有很多优化来改进这个算法。
随机化快排：快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取 第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较 常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情 况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可 以满足一个人一辈子的人品需求。”
　　随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直 接减弱。对 于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主 元保留在原位置。
平衡快排（Balanced Quicksort）：每次尽可能地选择一个能够 代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说， 选择这个数据的方法是取开头、结尾、中间3个数据，通过比较选出其 中的中值。取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近 似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微 打乱，破坏退化的结构。
对于快排优化的问题可以看看Java API(JDK)中的例子，参见《java.util.Arrays的排序研究》