[分享] 8种排序算法(有代码)

悠然南山

个人对这8种排序算法的理解,希望对大家有点帮助.
趁自修时间,自己将这8种排序的代码写了一下.......


1.简单的选择排序

1. bool selectionsort(int *array,int n)     //array为存储数据的数组,n为数组元素个数
   
2. {
   
3. int k,temp;        //k用来存储,临时最小数据的位置
   
4. for(int i=0;i<n-1;i++)     
   
5. {
   
6.   k=i;        
   
7.   for(int j=i+1;j<n;j++)    //从第i个数开始选择最小数位置,存于k中
   
8.    if(array[j]<array[k])
   
9.     k=j;
   
10.   if(k!=i)       //若最小数,不为array[i],则array[i]与array[k]进行交换
    
11.   {
    
12.    temp=array[i];
    
13.    array[i]=array[k];
    
14.    array[k]=temp;
    
15.   }
    
16. }
    
17. return true;
    
18. }

复制代码

思想:逐个找出,第一小,第二小....第n小的数...
算法平均时间复杂度: O(n^2)

2.插入排序

1. bool insertionsort(int *array,int n)
   
2. {
   
3. int temp;       //用来存储,插入的数据
   
4. for(int i=1;i<n;i++)  
   
5. {
   
6.   temp=array[i];    //用temp记录array[i]
   
7.   for(int j=i-1;j>=0;j--)  //逐个向前寻找插入点
   
8.   {
   
9.    if(temp>array[j])  //找到,跳出循环
   
10.     break;
    
11.    else     //没找到,将前一个数据后移
    
12.     array[j+1]=array[j];
    
13.   }
    
14.   array[j+1]=temp;
    
15. }
    
16. return true;
    
17. }

复制代码

思想: 逐个取数,插入一个有序数组(从后向前插)
算法平均时间复杂度: O(n^2)

悠然南山

3.自底向上排序

1. bool bottomupsort(int *array,int n)
   
2. {
   
3. int length=1,temp_length,i;           //temp_length表示单个合并数组的长度
   
4. while(length<n)
   
5. {
   
6.   temp_length=length;     //length表示合并后数组的长度
   
7.   length=2*temp_length;
   
8.   i=0;        //i用于记录合并数组的起始位置
   
9.   while(i+length-1<=n-1)           
   
10.   {
    
11.    merge(array,i,i+temp_length,i+length-1);  //合并i~i+temp_length-1 和 i+temp_length~i+length-1 段
    
12.    i=i+length;          //取下一个合并段的起始位置
    
13.   }
    
14.   if(i+temp_length<n-1)
    
15.    merge(array,i,i+temp_length,n-1);         //对尾部剩余段合并
    
16. }
    
17. return true;
    
18. }
    
19. bool merge(int *array,int start1,int start2,int n)  //合并两个有序数组
    
20. {
    
21. int temp_n=n-start1+1,       //两合并数组的长度和
    
22.   *temp_array,        
    
23.   n1=start2-1,        //第一个有序数组的末端位置
    
24.   temp_start1=start1;       //记录start1的初始位置
    
25. temp_array=(int *)malloc(sizeof(int)*temp_n);   //申请长度为temp_n的整形空间,用于临时存储合并后的数组
    
26.    
    
27. for(int i=0;start1<=n1&&start2<=n;i++)          //对两个有序数组进行合并,存储于temp_array
    
28. {
    
29.   if(array[start1]<=array[start2])
    
30.   {
    
31.    temp_array[i]=array[start1];
    
32.    start1++;
    
33.   }
    
34.   else
    
35.   {
    
36.    temp_array[i]=array[start2];
    
37.    start2++;
    
38.   }
    
39. }
    
40. if(start1<=n1)         
    
41. {
    
42.   while(start1<=n1)
    
43.   {
    
44.    temp_array[i++]=array[start1];
    
45.    start1++;
    
46.   }
    
47. }
    
48. else
    
49. {
    
50.   while(start2<=n)
    
51.   {
    
52.    temp_array[i++]=array[start2];
    
53.    start2++;
    
54.   }
    
55. }
    
56. for(i=0,start1=temp_start1;i<temp_n;start1++,i++)      //将合并后的有序数组,复制到array数组中
    
57. {
    
58.   array[start1]=temp_array[i];
    
59. }
    
60. free(temp_array);
    
61. return true;
    
62. }

复制代码

思想: 将数组的个部分,两两有序数组进行合并
算法平均时间复杂度: O(nlogn)

4.快速排序

1. void QuickSort(int low,int high,int *array)
   
2. {
   
3. int pos;
   
4. if(low<high)
   
5. {
   
6.   pos=SPLIT(low,high,array);     //以array[low]进行划分,pos最为划分点
   
7.              //前一部分<array[low],后一部分,反之
   
8.   QuickSort(low,pos-1,array);     //对划分后的前一部分递归处理
   
9.   QuickSort(pos+1,high,array);    //对划分后的后一部分递归处理
   
10. }
    
11. }
    
12. int SPLIT(int low,int high,int *array)
    
13. {
    
14. int temp=array[low];       //用temp来记录划分数
    
15. while(low<high)
    
16. {
    
17.   while(array[high]>temp&&low<high)      //寻找小于temp的数
    
18.    high--;
    
19.   if(low==high)
    
20.    break;
    
21.   else
    
22.   {
    
23.    array[low]=array[high];     
    
24.    low++;
    
25.   }
    
26.   while(array[low]<temp&&low<high)   //寻找大于temp的数
    
27.    low++;
    
28.   if(low==high)
    
29.    break;
    
30.   else
    
31.   {
    
32.    array[high]=array[low];
    
33.    high--;
    
34.   }
    
35. }
    
36. array[low]=temp;        //最终low=high作为划分点,并将划分数存于array[low]
    
37. return low;
    
38. }

复制代码

悠然南山

1. bool MergeSort(int low,int high,int *array)
   
2. {
   
3. int middle=(high+low)/2;     //将数组划分为2分
   
4. if(low<high)
   
5. {
   
6.   MergeSort(low,middle,array);   //对前一部分进行递归处理
   
7.   MergeSort(middle+1,high,array);   //对后一部分进行递归处理
   
8.   HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并
   
9. }
   
10. return true;
    
11. }
    
12. bool HeBing(int low1,int high1,int low2,int high2,int *array)
    
13. {
    
14. int *temp,
    
15.   i=low1,
    
16.   j=low2,
    
17.   k=0;
    
18. temp=(int *)malloc((high2-low1+1)*sizeof(int));   //temp用于临时存储合并后的数组
    
19. while(i<=high1&&j<=high2)        //对两个有序数组进行合并
    
20. {
    
21.   if(array[i]<array[j])
    
22.   {
    
23.    temp[k++]=array[i];
    
24.    i++;
    
25.   }
    
26.   else
    
27.   {
    
28.    temp[k++]=array[j];
    
29.    j++;
    
30.   }
    
31. }
    
32. if(i<=high1)
    
33. {
    
34.   while(i<=high1)
    
35.    temp[k++]=array[i++];
    
36. }
    
37. else
    
38. {
    
39.   while(j<=high2)
    
40.    temp[k++]=array[j++];
    
41. }
    
42. for(i=low1,j=0;i<=high2;i++,j++)                        //将合并后的数组,复制到array中
    
43. {
    
44.   array[i]=temp[j];
    
45. }
    
46. free (temp);
    
47. return true;
    
48. }

复制代码

思想:
就是你 从数组中 任取一个元素 p (可随机取,现在以取第一个为例)
以P作为主元,对数组 进行划分 ,前一部分小于 P,后一部分 大于p
最后 划分处 存储 p
然后分别对划分后的前一部分 和 后一部分 递归调用
算法平均时间复杂度: O(nlogn)

5.归并排序

悠然南山

1. bool MergeSort(int low,int high,int *array)
   
2. {
   
3. int middle=(high+low)/2;     //将数组划分为2分
   
4. if(low<high)
   
5. {
   
6.   MergeSort(low,middle,array);   //对前一部分进行递归处理
   
7.   MergeSort(middle+1,high,array);   //对后一部分进行递归处理
   
8.   HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并
   
9. }
   
10. return true;
    
11. }
    
12. bool HeBing(int low1,int high1,int low2,int high2,int *array)
    
13. {
    
14. int *temp,
    
15.   i=low1,
    
16.   j=low2,
    
17.   k=0;
    
18. temp=(int *)malloc((high2-low1+1)*sizeof(int));   //temp用于临时存储合并后的数组
    
19. while(i<=high1&&j<=high2)        //对两个有序数组进行合并
    
20. {
    
21.   if(array[i]<array[j])
    
22.   {
    
23.    temp[k++]=array[i];
    
24.    i++;
    
25.   }
    
26.   else
    
27.   {
    
28.    temp[k++]=array[j];
    
29.    j++;
    
30.   }
    
31. }
    
32. if(i<=high1)
    
33. {
    
34.   while(i<=high1)
    
35.    temp[k++]=array[i++];
    
36. }
    
37. else
    
38. {
    
39.   while(j<=high2)
    
40.    temp[k++]=array[j++];
    
41. }
    
42. for(i=low1,j=0;i<=high2;i++,j++)                        //将合并后的数组,复制到array中
    
43. {
    
44.   array[i]=temp[j];
    
45. }
    
46. free (temp);
    
47. return true;
    
48. }

复制代码

bool MergeSort(int low,int high,int *array)
{
int middle=(high+low)/2;     //将数组划分为2分
if(low<high)
{
  MergeSort(low,middle,array);   //对前一部分进行递归处理
  MergeSort(middle+1,high,array);   //对后一部分进行递归处理
  HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并
}
return true;
}
bool HeBing(int low1,int high1,int low2,int high2,int *array)
{
int *temp,
  i=low1,
  j=low2,
  k=0;
temp=(int *)malloc((high2-low1+1)*sizeof(int));   //temp用于临时存储合并后的数组
while(i<=high1&&j<=high2)        //对两个有序数组进行合并
{
  if(array<array[j])
  {
   temp[k++]=array;
   i++;
  }
  else
  {
   temp[k++]=array[j];
   j++;
  }
}
if(i<=high1)
{
  while(i<=high1)
   temp[k++]=array[i++];
}
else
{
  while(j<=high2)
   temp[k++]=array[j++];
}
for(i=low1,j=0;i<=high2;i++,j++)                        //将合并后的数组,复制到array中
{
  array=temp[j];
}
free (temp);
return true;
}
思想: 将数组划分为小数组,通过局部的有序合并,解决问题
算法平均时间复杂度: O(nlogn)

6.冒泡排序