时间戳

首页 > 技术文章 > 算法——排序方法总结（冒泡，快速，直接，希尔，堆，归并排序）

算法——排序方法总结（冒泡，快速，直接，希尔，堆，归并排序）

happying30 2018-08-23 16:17 原文

1、冒泡排序

　　分为单向起泡和双向起泡，单向可分为普通算法和改进算法

2、快速排序

　　快速排序思想：分治法（挖坑填数法+分治法）

　　排序效率：O(N*logN) 较高

0 1 2 3 4 5 6 7 8
12 9   13 11 20 17 15 10 18

 

 

　　初始时：i=0; j=4; t=Array[0]=12作为基准

　　从右向左：找到一个比t小的数，当j=7时，存放到Array[0]中

　　从左往右：找到一个比t大的数，当i=2时，存放到Array[7]中

　　最后将基准存放到Array[2]中

0 1 2 3 4 5 6 7 8
10 9   13 11 20 17 15 13 18

 

 

　　重复以上步骤，直到 i>=j 

0 1 2 3 4 5 6 7 8
10 9   11 12 20 17 15 13 18

 

 

　　再进行函数递归Array[0]到Array[2] 和 Array[4]到Array[8]

#include <stdio.h>
#include <stdlib.h>
int Partition(int *Array,int i,int j);
void QuickSort(int *Array,int Low,int High);
void main()
{
	int i,n;
	int Array[255];
	printf("请输入数据的个数：");
    scanf("%d",&n);
	if(n<0||n>255)
	{
	  printf("n is not correct!\n");
	  exit(1);
	}
	printf("请依次输入待排序数据：\n");
	for(i=0;i<n;i++)
	   scanf("%d",(Array+i));
	printf("\n请输出待排序数据\n");
	for(i=0;i<n;i++)
		printf("%d ",*(Array+i));
	QuickSort(Array,0,n-1);
		printf("\n请输出排序数据数据\n");
	for(i=0;i<n;i++)
		printf("%d ",*(Array+i));
	//printf("\n");
}

int Partition(int *Array,int i,int j)
{
	int t=*(Array+i);  //用第1位作基准，*（Array+0）
	while(i<j)
	{
		while(i<j&&*(Array+j)>=t)
			j--;
		if(i<j)
		{
		    *(Array+i)=*(Array+j);
			i++;
		}
	
		while(i<j&&*(Array+i)<=t)
			i++;
		if(i<j)
		{
			*(Array+j)=*(Array+i);
			j--;
		}
	}
	*(Array+i)=t;
	return i;
}

void QuickSort(int *Array,int Low,int High)
{
	int mid;
	if(Low<High)
	{
	mid=Partition(Array,Low,High);
	QuickSort(Array,Low,mid-1);
	QuickSort(Array,mid+1,High);
	}
}

　　

3、直接选择排序

void Selectsort(int *Array,int n)
{
   for(int i=0;i<n-1:i++)
     {
          int m=i;
          for(int j=i+1;j<n;j++)
             {
                   if(*(Array+j)<*(Array+m))
                     m=j;
               }
             if(m!=i)
              {
                    int a=*(Array+m);
                   *(Array+m)=*(Array+i);
                   *(Array+i)=a;
              }
     }  
}

　　

4、直接插入排序

　　第一次插入：Array[1]与Array[0]进行比较

　　第 i 次插入：先是Array[i]与Array[i-1]进行比较，如果小于，则将第Array[i-1]后移一位；如果大于则查找结束。

#include <stdio.h>
#include <stdlib.h.>
void InsertSort(int *Array,int n);
void main()
{
	int i, n;
	int Array[255];
	printf("请输入待输入数据个数：");
	scanf("%d",&n);
	printf("\n请输入待输入数据\n");
	for(i=0;i<n;i++)
		scanf("%d",(Array+i));
	printf("\n输出待排序数据\n");
	for(i=0;i<n;i++)
		printf("%d ",*(Array+i));
	InsertSort(Array,n);
		printf("\n输出排序好的数据\n");
	for(i=0;i<n;i++)
		printf("%d ",*(Array+i));
}

void InsertSort(int *Array,int n)
{
   int i,j,temp;
   for(i=1;i<n;i++)
   {
     if(*(Array+i)<*(Array+i-1))                         
	 {
		 j=i-1;
		temp=*(Array+i);                     
		do                         //do  while可改成for(j=i-1;j>0&&*Array[j]>temp;j--);  
		{                          //      Array[j+1]=Array[j];
		   *(Array+j+1)=*(Array+j);  
		   j--;
		}while(temp<*(Array+j));    
		*(Array+j+1)=temp;
	 }
   }
}

　　

5、希尔排序

6、堆排序

7、归并排序

图片来自<https://www.cnblogs.com/chengxiao/p/6194356.html#4002669>

#include<stdio.h>
void MergePass(int *a,int *b,int t,int n)
{
     int i,j,index;
    int beg1,end1;
    int beg2,end2;
    beg1=0;index=0;
    while(beg1+t<=n-1)
     {
        beg2=beg1+t;
        end1=beg2-1;
        if(beg2+t-1<=n-1)
             end2=beg2+t-1;
        else
             end2=n-1;
        i=beg1;
        j=beg2;
       while(i<=end1&&j<=end2)
          {
              if(*(a+i)<=*(a+j))
                  {
                     *(b+index)=*(a+i);
                       i++;
                       index++;
                  }
             else
                   {
                       *(b+index)=*(a+j);
                        j++;
                        index++;
                        
                    }
           }
      while(i<=end1)
             {
                  *(b+index)=*(a+i);
                   index++;
                   i++;
             }
         while(j<=end2)
              {
                  *(b+index)=*(a+j);
                   index++;
                   j++;
               }
              beg1=end2+1;
      }

       for(i=beg1;i<n;index++)
             *(b+index)=*(a+i);
 }

void MergeSort(int *a,int *b,int n)
{
   int i,j,count;
   j=1;count=1;
   while(j<n)
    {
      MergePass(a,b,j,n);
      for(i=0;i<n;i++)
        *(a+i)=*(b+i);
         j*=2;
     }
}

void main()
{
  int Array[]={10,50,20,30,40,60,90,80};
  int y[8];
  int i;
  MergeSort(Array,y,8);
  for(int i=0;i<8;i++)
    printf("%d ",*(Array+i));
}

程序二：（转自https://blog.csdn.net/morewindows/article/details/6678165白话算法之归并算法的实现）

#include <iostream>
using namespace std;

void mergearray(int a[], int first, int mid, int last, int temp[])
{
	int i = first, j = mid + 1;
	int m = mid,   n = last;
	int k = 0;
	
	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	
	while (i <= m)
		temp[k++] = a[i++];
	
	while (j <= n)
		temp[k++] = a[j++];
	
	for (i = 0; i < k; i++)
		a[first + i] = temp[i];

}
void mergesort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergesort(a, first, mid, temp);    //左边有序
		mergesort(a, mid + 1, last, temp); //右边有序
		mergearray(a, first, mid, last, temp); //再将二个有序数列合并
	}
}
 
//bool MergeSort(int a[], int n)
//{
//	int *p = new int[n];
//	if (p == NULL)
//		return false;
//	mergesort(a, 0, n - 1, p);
//	delete[] p;
//	return true;
//}
int main()
{
	int Array[]={8,4,5,7,1,3,6,2};
	int n=8;
	int *p=new int [n];
	mergesort(Array, 0, n - 1, p);
	for (int i = 0; i < n; i++)
	    cout<<" "<<Array[i];
}

　　

　(待续中...........)

推荐阅读