做动态网站难么/程序员培训机构哪家好

本文主要向大家介绍了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 

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 

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

for (j=i+1; 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 

while left  tmp:

right -= 1

lists[left] = lists[right]

left += 1

while left 

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 

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 

while(start_index  tmp){

end_index--;

}

if(start_index 

ar[start_index] = ar[end_index];

start_index++;

}

while(start_index 

start_index++;

}

if(start_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] 

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 

minIndex = i;

for (j = i+1; j

if(ar[j] 

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  lists[max_index]:

max_index = left_child

if 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 

maxIndex = 2*root+1  ar[root] ? 2*root+1 : root;

maxIndex = 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+频道！