算法复习之排序

一。STL中的sort

传入迭代器类型可以传入伪函数用于自定义类型比较

STL中多种排序函数：详细解说STL排序

二.自己实现排序：

1.快速排序:

基本思想：定义i,j类似两个哨兵，确定一个基准数

分别从要排序数组头尾出发遍历从左到右找大于，从右到左找小于，交换，最后保证大于基准数的在右边，小于基准数的在左边

之后左右区间重复上面步骤直到各区间只有一个数。

 1 #include<iostream>
 2 using namespace std;
 3 void Quick_Sort(int *a,int left,int right)
 4 {
 5     int i,j;
 6     if(left>right)
 7     return;
 8     int temp;//基准数  快速排序1的优化的一个方面在于基准数的选择，先选最左面为基准数
 9     temp=a[left];
10     i=left;
11     j=right;
12     while(i!=j)    //i,j两个没有相遇
13     {
14       while(a[j]>=temp&&i<j)
15       j--;
16       while(a[i]<=temp&&i<j)
17       i++;
18       if(i<j)
19       {
20           int t=a[i];
21           a[i]=a[j];
22           a[j]=t;
23       }
24     } 
25     a[left]=a[i];
26     a[i]=temp;     //基准数归位
27     Quick_Sort(a,left,i-1);
28     Quick_Sort(a,i+1,right);
29     return; 
30 }
31 int main()
32 {
33     int a[8]={1,8,5,9,3,7,6,5};
34     Quick_Sort(a,0,7);
35     for(int i=0;i<8;i++)
36     cout<<a[i]<<" ";
37     cout<<endl;
38     return 0;
39 }

针对快排的优化：

1）.选择基准数时。，三数取中：对left,mid,right,三位排序，取中间数

2）.当分治到长度较小时，使用插入排序

3）.在一次分割后，可以把与基准值相同的元素聚在一起，继续下次分割时，不用再对与其相同元素进行分割。

2.插入排序

基本思想：就像发牌时抽牌，一部分是已经抽好的放在手上，一部分还在桌上，现在从桌上的牌取一张与手上已经排好序的牌比较，找到位置插入。

 1 #include<iostream>
 2 using namespace std;
 3 void Insert_Sort(int *a,int a_length)
 4 {
 5     int i,j;
 6     for(j=1;j<a_length;j++){
 7         int key=a[j];
 8         i=j-1;
 9         while(i>=0&&a[i]>key)
10         {
11             a[i+1]=a[i];
12             i--;
13         }
14         a[i+1]=key;
15     }
16 }
17 int main()
18 {
19     int a[10]={1,8,5,6,0,2,3,4,10,6};
20     Insert_Sort(a,10);
21     for(int i=0;i<10;i++)
22     cout<<a[i]<<" ";
23     cout<<endl;
24     return 0;
25 }

3.归并排序

采用分治

欲使整体序列有序，先使子序列有序，而后归并

void Merge(int *a,int *temp,int start,int end)
{
    if(start>=end) return;
    int len=end-start,mid=(len>>1)+start;
    //分成两个子区间,递归下去，直到每个子区间只有一个数 
    int start1=start,end1=mid;
    int start2=mid+1,end2=end;
    Merge(a,temp,start1,end1);
    Merge(a,temp,start2,end2);
    //然后比较，归并，temp用于保存中间结果
    int k=start;
    while(start1<=end1&&start2<=end2)
    temp[k++]=a[start1]<a[start2]?a[start1++]:a[start2++];
    //如果比较后有剩余部分，则全部合并上去
    while(start1<=end1)
    temp[k++]=a[start1++];
    while(start2<=end2)
    temp[k++]=a[start2++];
    //最后再换回去
    for(k=start;k<=end;k++)
    a[k]=temp[k]; 
}

void Merge_Sort(int a,int len)
{
    int temp[len]={0};
    Merge(a,temp,0,len-1);
}

4.冒泡排序最熟悉的排序

 1 #include<iostream>
 2 using namespace std;
 3 void Bubble_Sort(int *a,int len)
 4 {
 5     for(int i=0;i<len-1;i++)
 6     for(int j=0;j<len-i-1;j++)
 7     {
 8         if(a[j]>a[j+1])
 9         {
10             int temp=a[j];
11             a[j]=a[j+1];
12             a[j+1]=temp;
13         }
14     }
15 }
16 
17 int main()
18 {
19     int a[10]={1,0,2,8,5,9,6,7,2,1};
20     Bubble_Sort(a,10);
21     for(int i=0;i<10;i++)
22     cout<<a[i]<<" ";
23     cout<<endl;
24     return 0;
25 }

5.堆排序