感谢cnblog@一像素  是他的BLOG帮助我更加清楚的认识了排序算法

 

排序算法的分类

十大排序算法及代码实现(C++)-LMLPHP


 

排序算法的复杂度分析

十大排序算法及代码实现(C++)-LMLPHP


相关概念补充:

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。(不稳定则反之)


1.直接插入排序(Insertion Sort)

工作原理:取出元素与序列中的其他元素比较后插入

代码实现:

void inserttionsort(){
	for(int i=1;i<=arraysize;i++){
		int pre=i-1;//当前取出的元素的前一个
                int now=a[i];//当前元素的值
		while(pre>0&&a[pre]>now){
			a[pre+1]=a[pre];
			now--;
		}
        a[pre+1]=now;
	}
}

2.希尔排序(Shell Sort)

工作原理:分割为几个序列分别进行直接插入排序

改进后的插入排序,区别在于将每次步进的长度改为合适值

代码实现:

void shellsort(){
	int shell=arraysize>>1;;//希尔值一般初始化为序列长度的一半
	while(shell!=0){
		for(int i=1;i<=n;i+=shell){
		        int pre=i-shell;
                        int now=a[i];
		        while(pre>0&&a[pre]>now){
			       a[pre+shell]=a[pre];
			       pre=pre-shell;
		        }
	        }
	    shell=shell>>1;
       }
}
	

3.冒泡排序(Bubble Sort)

工作原理:从头走到尾,如果两元素逆序则交换,一直循环

代码实现:

void bubblesort(){
	for(int i=1;i<n;i++){
	    int ok=0;
	    for(int i=1;i<n;i++){
	 	 if(a[i]>a[i+1]){
	 	 	ok=1;
	 	 	swap(a[i],a[i+1]);
		  }
	    }
	    if(!ok)return;
	}
}

4.选择排序(Selection Sort)

工作原理:找出最小的放在队首

代码实现:

void choosesort(){
     for(int i=1;i<=n;i++){
         int now=a[i],cur=i;
         for(int j=i;j<=n;j++){
             if(a[j]<now){
                 now=a[j];
                 cur=j;
             }
         }
         swap(a[i],a[cur]);
}

5.归并排序(Merge Sort)

工作原理:分割序列分别排序后合并

代码实现:

void merge(int l,int mid,int r){
	int i=l,j=mid+1;
	int t=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j]) b[t++]=a[i++];
		else b[t++]=a[j++];
	}
	while(i<=mid) b[t++]=a[i++];
	while(j<=r) b[t++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}

void mergesort(int l,int r){
	if(l<r){
		int mid=(l+r)/2;
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r);
	}
}

6.快速排序(Quick Sort)

工作原理:设置两哨兵标记逆序元素

代码实现:

void quicksort(int l,int r){
    int i,j,mid;
    i=l;j=r;
    mid=a[(i+j)/2];
    while(i<=j){
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(l<j)quicksort(l,j);
    if(i<r)quicksort(i,r);
}

7.堆排序(Heap Sort)

工作原理:利用近似完全二叉树(保证子结点的值小于父节点)

代码实现:

int left(int n){
    return n*2;
}

int right(int n){
    return n*2+1;
}

void maxheapify(int i){//调整堆
    int l=left(i);
    int r=right(i);
    int largest;
    if(l<=heapsize&&a[l]>a[i])
     largest=l;
    else largest=i;
	if(r<=heapsize&&a[r]>a[largest])
	 largest=r;
	if(largest!=i)
	{
		swap(a[i],a[largest]);
	    maxheapify(largest);
	}
}

void buildmaxheap(){//初始化最大堆
	heapsize=n;
	for(int i=n/2;i>=1;i--)
	 maxheapify(i);
}

void heapsort(){
    buildmaxheap();
    for(int i=n;i>=2;i--){
    	swap(a[1],a[i]);
    	heapsize--;
    	maxheapify(1);
	}
}

余下的线性时间排序待本人有时间再继续更啦 溜了

10-06 20:43