摘要:本文主要向大家介绍了C/C++知识点之排序算法(C语言+Python版)宝宝再也不怕面试官写排序算法了,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之排序算法(C语言+Python版)宝宝再也不怕面试官写排序算法了,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
直接插入排序过程: 1. 数据可分看成两个部分,前面的数据是有序的 2. 从后面的数据取出一个元素,插到前面有序数据的合适位置 从右端开始查找,到找到比此元素大的时候,则此元素向后移动,以空出多余的空间来插入此元素。 3. 查找至最后。
例: 3 2 4 5 8 1 2 3 4 5 8 1 1 2 3 4 5 8
def insert_sort(lists):
count = len(lists)
for i in range(1, count):
tmp = lists[i]
j = i - 1
while j >= 0 and lists[j]>tmp:
lists[j+1] = lists[j]
j -= 1
lists[j+1] = tmp
return lists
void direct_insert_sort(int *ar, int count);
void direct_insert_sort(int *ar, int count){
int tmp;
int i;
int j;
for (i=1; i < count; i++){
tmp = ar[i];
j = i-1;
while(j>=0 && (ar[j] > tmp) ){
ar[j+1] = ar[j];
j--;
}
ar[j+1] = tmp;
}
}
希尔排序
过程: 1.将所有的数据分组为N/2;这样每组就有2个数据,利用直接插入排序。 2.将所有的数据分组为N/2*2; 每组就有4个数据,利用直接插入排序。 3.step大于等于1,最后再一次直接插入排序
评价: 1. 时间复杂度:n^1.25 或者 nlog2(n) 2. 非稳定 3. 插入排序对于“局部有序”有较好的表现
def shell_sort(lists):
count = len(lists)
step = count/2
while step>0:
for i in range(step, count, step):
tmp = lists[i]
j = i - step
while j >= 0 and lists[j] > tmp:
lists[j+step] = lists[j]
j -= step
lists[j+step] = tmp
step/=2
return lists
void inner_direct_insert_sort(int *ar, int count, int step);
void shell_sort(int *ar, int count);
void shell_sort(int *ar, int count){
int step;
for (step=count/2; step > 0; step/=2)
inner_direct_insert_sort(ar, count, step);
}
// 调用插入排序,但是这里需要改变步长。
void inner_direct_insert_sort(int *ar, int count, int step){
int tmp;
int i;
int j;
for (i=step; i < count; i+=step){
tmp = ar[i];
j = i-step;
while(j>=0 && (ar[j] > tmp) ){
ar[j+step] = ar[j];
j-=step;
}
ar[j+step] = tmp;
}
}
冒泡排序:
哈哈最简单了
1. 从头开始,依次和自己后面的元素进行比较,交换
时间复杂度也很高O(N)
def bubble_sort(lists):
count = len(lists)
for i in range(0, count):
for j in range(i+1, count)
if lists[i] > lists[j]:
lists[i], lists[j] = lists[j], lists[i]
return lists
void bubble_sort(int *ar, int count);
void bubble_sort(int *ar, int count){
int i;
int j;
int tmp;
for(i=0; i<count; i++){
for (j=i+1; j<count; j++){
if(ar[i] > ar[j]){
tmp = ar[i];
ar[i] = ar[j];
ar[j] = tmp;
}
}
}
}
快速排序
过程:1、基本的步骤 首先确定参考元素,参考元素左边是比参考元素小的元素,参考元素右边是比参考元素大的元素; 即参考元素把数据分成两部分 先设参考
2、递归调用基本的步骤
评价:时间复杂度:O(N*log2N)稳定性:非稳定 如果第一个参考元素比后面的有多个元素大,则排序之后逆序 如果第一个参考元素比后面的有多个元素小,则排序之后顺序
最差情况:完全逆序、完全顺序
def quick_sort(lists, left, right):
if left >= right:
return lists
tmp = lists[left]
start = left
end = right
while left < right:
while left < right and lists[right] > tmp:
right -= 1
lists[left] = lists[right]
left += 1
while left < right and lists[left] < tmp:
left += 1
lists[right] = lists[left]
right -= 1
lists[left] = tmp
quick_sort(lists, start, left-1)
quick_sort(lists, left+1, end)
return lists
l = [3,1,2,4,5,45,43,634534,5,4,4,324,5,2,4,32,4,5,422,52,42,42,421]
print quick_sort(l,0,len(l)-1)
int base_action(int *ar, int start_index, int end_index);
void inner_quick_sort(int *ar, int start_index, int end_index);
void quick_sort(int *ar, int count);
void quick_sort(int *ar, int count){
inner_quick_sort(ar, 0, count-1);
}
void inner_quick_sort(int *ar, int start_index, int end_index){
int mid_index;
if(start_index < end_index){
mid_index = base_action(ar, start_index, end_index);
inner_quick_sort(ar, start_index, mid_index-1);
inner_quick_sort(ar, mid_index+1, end_index);
}
}
int base_action(int *ar, int start_index, int end_index){
int tmp;
tmp = ar[start_index];
while(start_index < end_index){
while(start_index < end_index && ar[end_index] > tmp){
end_index--;
}
if(start_index < end_index){
ar[start_index] = ar[end_index];
start_index++;
}
while(start_index < end_index && ar[start_index] < tmp){
start_index++;
}
if(start_index < end_index){
ar[end_index] = ar[start_index];
end_index--;
}
}
ar[start_index] = tmp;
return start_index;
}
直接选择排序过程: 1. 先在所有的元素中选出最值,则当前的第一个元素交换,即放到有序的集合里面; 2. 再在后面剩余的元素中找出最值,放到之前的有序集合里面。注意,是放在有序集合的最右边; 2.1 选取下一个节点为参考元素,接着和剩余的元素作比较,选出最值的下标。 2.2 循环完成,就选择出了最值了。 2.3 检测最值的下标和之前的参考元素的下标是否相同,如果相同的话,说明中间并没有改变, 也就是说参考元素就是最值。 如果最值的下标和之前的参考元素的下标不同,则交换元素。
评价: 1. 时间复杂度:O( (1+n-1)n/2) ==>O(n*n) 2. 非稳定的 3. 完全升序,交换次数最少 4. 完全逆序,交换次数不是最多;
def select_sort(lists):
count = len(lists)
for i in range(0, count):
min_index = i
for j in range(i+1, count):
if lists[j] < lists[min_index]:
min_index = j
lists[i],lists[min_index] = lists[min_index], lists[i]
return lists
void direct_select_sort(int *ar, int count);
void direct_select_sort(int *ar, int count){
int tmp; //用于交换的中间值
int i; //下一个要比较的元素,即参考元素
int j; //除了已排好序的集合和下一个元素,剩下的所有元素的都和下一个元素比较
int minIndex; //最小的值的下标,将来放到已排好的元素中去
for (i=0; i < count-1; i++){
minIndex = i;
for (j = i+1; j<count; j++){
if(ar[j] < ar[minIndex] ){
minIndex = j;
}
}
if (minIndex != i){
tmp = ar[minIndex];
ar[minIndex] = ar[i];
ar[i] = tmp;
}
}
}
堆排序
过程:1、将整个的数据,调整成大根堆。(大根堆:根节点大于左右节点,调整过程深度优先) 这里提下完全二叉树的性质 设总结点为count 叶子节点数量:(count+1)/2 非叶子节点数量: count - (count+1)/2 = (count-1)/2 最后一个非节点: (count-1)/2 - 12、将根节点和最后一个叶子节点交换。之后再次调整整棵数为大根堆3、直到只有一个根节点
评价:1. 非稳定2. O(N·log2N)3. 完全顺序:小跟堆,最差情况4. 完全逆序:大根堆,比较次数不变。最优情况
def adjust_head(lists, root, count):
not_finished = True
while not_finished and root <= (count-1)/2:
max_index = root
left_child = 2*root + 1
right_child = 2*root + 2
if left_child < count and lists[left_child] > lists[max_index]:
max_index = left_child
if right_child < count and lists[right_child] > lists[max_index]:
max_index = right_child
if root != max_index:
lists[root], lists[max_index] = lists[max_index], lists[root]
else:
not_finished = False
root = max_index
def heap_sort(lists):
count = len(lists)
last_not_leaf_node = (count-1)/2
for root in range(last_not_leaf_node, -1, -1):
adjust_head(lists, root,count) #调整为大跟堆
while count > 1:
lists[count-1], lists[0] = lists[0], lists[count-1]
count -= 1
adjust_head(lists,root, count)
return lists
void adjustBigHeap(int *ar, int count, int root);
void heapSort(int *ar, int count);
void heapSort(int *ar, int count){
int root;
int tmp;
for(root = (count-1)/2-1; root > 0; root--){
adjustBigHeap(ar, count, root);
}
while(count > 1){
adjustBigHeap(ar, count, root);
tmp = ar[0];
ar[0] = ar[count-1];
ar[count-1] = tmp;
count--;
}
}
void adjustBigHeap(int *ar, int count, int root){
int maxIndex;
int tmp;
boolean finished = FALSE;
while(!finished && maxIndex < (count-1)/2){
maxIndex = 2*root+1 < count && ar[2*root+1] > ar[root] ? 2*root+1 : root;
maxIndex = 2*root+2 < count && ar[2*root+2] > ar[maxIndex] ? 2*root+2 : maxIndex;
if(maxIndex != root){
tmp = ar[root];
ar[root] = ar[maxIndex];
ar[maxIndex] = tmp;
}else{
finished = TRUE;
}
root = maxIndex;
}
}
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号