[分享]排序算法总结_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2667 | 回复: 0   主题: [分享]排序算法总结        上一篇   下一篇 
huang.wang
注册用户
等级:中将
经验:17623
发帖:407
精华:1
注册:1970-1-1
状态:离线
发送短消息息给huang.wang 加好友    发送短消息息给huang.wang 发消息
发表于: IP:您无权察看 2018-10-22 16:09:48 | [全部帖] [楼主帖] 楼主


    本文转自 Yikun博客


    1. 概述 


算法名称复杂度实现关键
冒泡排序O(n^2)(无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。
选择排序O(n^2)(有序区,无序区)。在无序区里选择一个最小的元素跟在有序区的后面。
插入排序O(n^2)(有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。
希尔排序nlog^2(n)每一轮按照事先决定的间隔进行插入排序,间隔会依次缩小,最后一次一定要是1(插入)。
快速排序nlog(n)(小数,枢纽元,大数)。
堆排序nlog(n)
桶排序O(n)将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。


不稳定的排序:稳定性一个形象的比喻,本来有两个并列第三,一排序把原来并列的顺序给变了。 比如:选择排序、快速排序、堆排序、希尔排序; 


    2. 冒泡排序 


每次都把未排序的第一个作为起始点,然后逐渐冒泡上升,之后未排序区越来越少,最终排序完成 


image.png


// 冒泡排序 
void bubble_sort(int a[], int n) 
{ 
int i = 0; 
int j = 0; 
for (i=0; i<n-1; i++) 
{ 
// 比较相邻元素,若a[j]比a[j+1]大,则交换 
// a[j]就像一个气泡一样“浮”到合适位置了 
for(j=0; j<n-1-i; j++) 
{ 
if(a[j]>a[j+1]) 
{ 
swap(&a[j], &a[j+1]); 
} 
} 
} 
}


    3. 选择排序 


每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 


image.png


// 选择排序 
void select_sort(int a[], int n) 
{ 
int i=0,j=0,min=0; 
for (i=0; i < n-1; i++) 
{ 
min = i; 
// 找到最小值 
for (j=i+1; j <= n-1; j++) 
{ 
if (a[min] > a[j]) 
min = j; 
} 
if(min != i) 
{ 
swap(&a[min], &a[i]); 
} 
} 
}


    4. 插入排序 


每次排序从未排序区取一个“牌”,然后往前插入(包括了两步:大的往后移,把牌放到合适位置)。 

// 插入排序 
void insert_sort(int a[], int n) 
{ 
int i=0; 
int j=0; 
int tmp=0; 
for (i = 1; i < n; i++) 
{ 
// 取牌 
tmp = a[i]; 
// 往前插的起始位置 
j = i - 1; 
// 大的a[j]都放后面,寻找出j 
while ((j >= 0) && a[j] > tmp) 
{ 
// 往后放一个 
a[j+1] = a[j]; 
j--; 
} 
// 放到该放的位置 
a[j+1]=tmp; 
} 
}


另外还有种思路,把数据后移的过程换成交换的过程 


// 插入排序,选中的牌冒泡向前插入 
void insert_sort_2(int a[], int n) 
{ 
int i=0; 
int j=0; 
//通过i选牌 
for (i=1; i < n; i++) 
{ 
// 冒泡向前插入(i-1 --> 0) 
for (j=i-1; j>=0 && a[j] > a[j + 1]; j--) 
{ 
swap(&a[j], &a[j+1]); 
} 
} 
print_a(a, n); 
}


    5. 希尔排序 


对插入排序再加一个步长的循环就是希尔排序了,例如 


[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]


按照5步长排序,则相当于按列先进行排序(实际是通过下标实现的) 


13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10


排序后结果为 


10 14 73 25 23 
13 27 94 33 39 
25 59 94 65 82 
45


多次循环后,只需要最终步长为1即可。 


// 希尔排序 
void shell_sort(int a[], int n) 
{ 
int i=0; 
int j=0; 
int tmp=0; 
int gap=0; 
while (gap <= n) 
{ 
gap = gap*3 + 1; 
} 
while (gap > 0) 
{ 
// 取牌 
for (i = gap; i < n; i++) 
{ 
// 冒泡向前插入(i-gap : gap : 0), 保证每列ok 
for (j = i - gap; (j >= 0) && (a[j] > a[j + gap]); j = j - gap) 
{ 
swap(&a[j], &a[j+gap]); 
} 
} 
gap = (gap-1) / 3; 
} 
}


    6. 快速排序 


每次迭代都选出一个基准,左边放小的,右边放大的,最终迭代完成。 


image.png


// 快速排序分区 
static int partition(int a[], int p, int r) 
{ 
int x=0; 
int i=0; 
int j=0; 
// x为基准 
x = a[r]; 
// i为界限,发现小于x的,就i++,再放到i处 
i = p-1; 
for (j=p; j<= r-1; j++) 
{ 
if (a[j]<=x) 
{ 
i++; 
swap(&a[i], &a[j]); 
} 
} 
// 至此,所有小于x的都到i左边了(a[0]~a[i-1]),a[r]是x,因此交换a[i+1]和a[r] 
swap(&a[i+1], &a[r]); 
return i+1; 
} 
// 快速排序 
void quick_sort(int a[], int p, int r) 
{ 
int q=0; 
if (p < r) 
{ 
// 在数据集之中,选择一个元素作为"基准"(pivot) 
// 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边 
q = partition(a, p, r); 
// 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。 
quick_sort(a, p, q-1); 
quick_sort(a, q+1, r); 
} 
}



该贴被huang.wang编辑于2018-10-22 16:14:36


我超级酷,但是如果你回复我的话我可以不酷那么一小会儿。


——来自logo.png


赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论