• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

排序算法合集(C++实现)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

排序操作在程序设计中是非常基础和常见的,也是算法的基础部分,我对几种常见的比较排序算法进行了整理。

选择排序

思想:遍历数组,每次遍历都在未排序的部分找到最小元素的下标,在此次遍历结束后将最小元素放到遍历开始的位置。

性能:时间复杂度为O(n2),算法比较次数与初始序列状态无关,性能在所有排序算法中最差。

 

void Violence_Sort(int* A, int len){
        for(int i=0;i<len;i++)
        {
                int k = i;
                for(int j=i;j<len;j++)
                        if(A[j]<A[k])
                                k = j;
                if(k != i){
                        int t = A[i];
                        A[i] = A[k];
                        A[k] = t;
                }
        }
}

 

插入排序(insert sort)

思想: 将当前元素与它前面已排好序的元素依次进行比较,最后放置在合适的位置,初始时可从第二个元素开始,认为第一个元素已排好序。

性能:算法时间复杂度为O(n2),在序列规模较小时,性能比较好,且元素比较次数与初始序列杂乱程度相关,最优复杂度为O(n)。

 

void Insert_Sort(int* A, int len){
        for(int i=1;i<len;i++)
        {
                int key = A[i];
                int j = i - 1;
                while(j >= 0 && key  < A[j]){
                        A[j+1] = A[j];
                        j--;
                }
                A[j+1] = key;
        }
}

 

希尔排序(shell sort)

思想:利用插入排序的思想,考虑到插入排序在序列基本有序且数量较少时性能较高,因此先对序列进行逻辑上的分组然后插入排序,如:设定初始增量为x,则0,0+x,0+x+x ...为一组,1,1+x,1+x+x ...为第二组,共有x组,分别进行排序。那个随后减少增量,增加分组,直到增量为1。

性能:算法时间复杂度为O(n1.3) -O(n2),性能取决于增量序列。

void shellSort(int A[], int len){
    for(int gap = len/2; gap > 0; gap /= 2){
        for(int i = gap; i < len; i++){
            int key = A[i];
            int j;
            for(j = i-gap; j>=0 && A[j] > key; j-= gap)
                A[j+gap] = A[j];
            A[j+gap] = key;
        }
    }
}

 

 

冒泡排序(bubble sort) 

思想:从左往右遍历,比较相邻两个元素的大小,将大的一个放在后面,每遍历一趟,可找到一个最大值放置在最后,经过n-1趟遍历即可。

性能:时间复杂度为O(n2),元素比较次数与初始状态无关,性能略低于插入排序。

 

void Bubble_Sort(int* A,int len){
        for(int i=1;i<len;i++)
                for(int j=0;j<len-i;j++)
                {
                        if(A[j]>A[j+1]){
                                int t = A[j+1];
                                A[j+1] = A[j];
                                A[j] = t;
                        }
                }
}

 

归并排序(merge sort)

思想:使用分治思想,将原始序列分为两部分分别排序,然后合并,重点在于合并过程。

性能:时间复杂度为O(nlgn),不过合并过程会使用额外的存储空间,占用内存。

 

void Merge(int A[], int low, int mid, int high){
        int cp[high-low+1];
        for(int i = low; i <= high; i++)
            cp[i-low] = A[i];
        int l = low, r = mid+1;
        for(int i = low; i <= high; i++){
            if(l > mid) {A[i] = cp[r - low]; r++;}
            else if(r > high) {A[i] = cp[l - low]; l++;}
            else if(cp[l-low] <= cp[r-low]) {A[i] = cp[l -low]; l++;} 
            else {A[i] = cp[r -low]; r++;}
        }
}    

void Merge_Sort(int A[], int low, int high){
        if(high > low){
                int mid = (low+high)/2;
                Merge_Sort(A, low, mid);
                Merge_Sort(A, mid+1, high);
                Merge(A, low, mid, high);
        }
}

 

 

 

 

快速排序(quick sort)

思想:与归并排序类似,也使用分治思想,选择一个元素值(一般选择最后一个元素),将比它小的放在左边部分,比它大的放在右边,然后对两部分分别进行上述操作知道递归结束,关键步骤在于元素的分类,且只占用O(1)的额外存储空间。

性能:时间复杂度为O(nlgn),与归并排序不同,该算法占用常数级额外存储,在大规模序列排序应用中性能较好。

 

int patition(int* p, int left, int right){
    int key = p[left];
    while(left < right){
        while(left<right && key <= p[right]) right--;
        if(left<right) p[left++] = p[right];
        while(left<right && key >= p[left]) left++;
        if(left<right) p[right--] = p[left];
    }
    p[left] = key;
    return left;
}

void quick_sort(int* p, int left, int right){
    if(left >= right) return;
    int mid = patition(p, left, right);
    quick_sort(p, left, mid-1);
    quick_sort(p, mid+1, right);
}

 

 

 

堆排序(heap sort)

思想:使用堆数据结构进行排序,堆是一种用数组存储的二叉树,根据父节点和子节点的大小关系分为最大堆和最小堆,这里使用最大堆进行排序。

性能:时间复杂度为O(nlgn),在实际使用中,堆排序的排序性能通常逊与快速排序。

void Max_Heapify(int* A, int i,int size){
        int l = 2*i;
        int r = 2*i + 1;
        int large = i;
        if(l <= size && A[l] > A[i])
                large = l;
        else
                large = i;
        if(r <= size && A[r] > A[large])
                large = r;
        if(large != i){
        int t = A[large];
        A[large] = A[i];
        A[i] = t;
        Max_Heapify(A, large, size);
        }
}

void Build_Max_Heap(int* A, int size){
        for(int i=size/2;i>0;i--)
                Max_Heapify(A,i,size);
}
  
void Heap_Sort(int* A, int len){
        Build_Max_Heap(A, len);
        while(len-1){
                int t = A[1];
                A[1] = A[i];
                A[i] = t;
                len--;
                Max_Heapify(A,1,len);
        }
}

  

 

 

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
asp.net(c#)GridView实现鼠标悬停高亮显示发布时间:2022-07-14
下一篇:
c#linq学习发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap