天道酬勤,学无止境

Quick Sort on a Linked List with a random pivot in C

I have spent a lot of time trying to work on this problem for a class and am at ends. I have found lots of resources regarding arrays and other ways of selecting a pivot but I am just at ends and am really going crazy here, any help would be so much appreciated you can not possibly imagine.

#include <stdlib.h>     /*and, malloc*/
#include <stdio.h>      /*printf*/


struct listnode {

    struct listnode *next;
    long value;
};

/*Finds length of list, which is usefull in selecting a random pivot*/
int ListLength (struct listnode *list)
{
    struct listnode *temp = list;

    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->next;

    }
    return i;
}

/*Prints list*/
void printList(struct listnode *list)
{   
    struct listnode *node;
    node=list;
    printf("\nList Values\n");
    while(node!=NULL)
    {
        printf("%2lo ", node->value);
        node=node->next;
    }
}
/*Creates a list of desired length*/
struct listnode *createList(int lengthOfList)
{
    long i; 
    struct listnode *node, *space;
    space =  (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
    for( i=0; i< lengthOfList; i++ )
    {  (space + i)->value = 2*((17*i+1)%lengthOfList);
       (space + i)->next = space + (i+1);
    }

    (space+(lengthOfList-1))->next = NULL;
    node = space;

    return node;
}

/*Prof Brass's test*/
void Brass_test(struct listnode *list)
{
    int i;
    printf("\nChecking sorted list\n");
    for( i=0; i < 100; i++)
    {  
        if( list == NULL )
        { 
            printf("List ended early\n"); exit(0);
        }
        if( list->value != 2*i )
        {  
            printf("Node contains wrong value\n"); exit(0);
        }
        list = list->next;
   }
   printf("Sort successful\n");
}

/*Selects a random pivot point*/
struct listnode *SelectPivot(struct listnode *list)
{

    int k, n, i = 0;
    n = ListLength(list);


    struct listnode *pivot=list;

    k=rand()%n;

    for (; i < k; ++i)
    {
        pivot=pivot->next;
    }

    return pivot;
}

// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;

    struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;

    /*Select a random pivot point*/
    struct listnode *pivot = SelectPivot(list);

    printf("Pivot Value = %lo\n", pivot->value);



    /*Divide & Conquer*/
    while(temp != NULL)
    {

        next = temp->next;

        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else 
        {
            temp->next = more;
            more = temp;

        }
        temp = next;
    }



    less = Quicksort(less);
    more = Quicksort(more);

    // Merge
    if(ListLength(less)!=0)
    {       
        while(endl != NULL)
        {
            endl = less->next;
            less->next = more;
            more = less;
            less = endl;
        }

        return more;        
    }
    else 
    {


        return more;    
    }

}

int main(void)
{
    struct listnode *node;

    node = createList(25);

    printf("Unsorted List\n");
    printList(node);

    printf("\nSorted List\n");
    node =  Quicksort(node);


    printf("\nList Count node %d\n", ListLength(node));
    printList(node);

   /* Brass_test(node);*/




    exit(0);
}

评论

So here is the the solution to the problem for those that are curious about the code. I included only the function its self and the helper functions.

Cheers,

#include <stdlib.h>     //rand, malloc
#include <stdio.h>      //print
#include <time.h>

struct listnode {

    struct listnode *next;
    long value;
};

//Finds length of list, which is usefull in selecting a random pivot
int ListLength (struct listnode *list)
{
    struct listnode *temp = list;
    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->next;
    }
    return i;
}

// Selects a random pivot point
struct listnode *SelectPivot(struct listnode *list)
{
    int k, n, i = 0;
    n = ListLength(list);
    struct listnode *pivot=list;
    k=rand()%n;  //
    for (; i < k; ++i)
    {
        pivot=pivot->next;
    }
    return pivot;
}

// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;
    struct listnode *less=NULL, *more=NULL, *next, *end, *temp=NULL;

    // Select a random pivot point
    struct listnode *pivot = SelectPivot(list);

    // Remove pivot from list
    while(list !=NULL)
    {
        next = list->next;

        if(list->value != pivot->value)
        {
            list->next=temp;
            temp = list;
        }
        list = next;
    }

    // Divide & Conq
    while(temp != NULL)
    {
        next = temp->next;
        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else 
        {
            temp->next = more;
            more = temp;    
        }
        temp = next;
    }

    // Recursive Calls
    less = Quicksort(less);
    more = Quicksort(more);

    // Merge
    if(less != NULL)
    {
        end = less;
        while(end->next != NULL){
            end=end->next;
            }
        pivot->next=more;
        end->next = pivot;
        return less;        
    }
    else{
        pivot->next = more;
        return pivot;   
    }

}

One problem is with your merge code -- it reverses the less list while prepending it to the more list, which results in garbage.

In case of applying quick sort, the best practice is always to take the FLOOR(n/2) As pivot

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 为什么Quicksort比mergesort更好?(Why is quicksort better than mergesort?)
    问题 采访中有人问我这个问题。 它们都是O(nlogn),但是大多数人都使用Quicksort而不是Mergesort。 这是为什么? 回答1 Quicksort具有O( 2 )最坏情况的运行时和O( log )平均情况的运行时。 但是,在许多情况下合并排序会更好,因为许多因素会影响算法的运行时间,并且将它们放在一起时,quicksort会胜出。 特别是,经常引用的排序算法运行时是指执行比较或对数据进行排序所需的交换次数。 这确实是一个很好的性能衡量标准,尤其是因为它独立于底层硬件设计。 但是,其他因素(例如引用的局部性(即,我们是否读取了很多可能在缓存中的元素?))在当前硬件上也起着重要作用。 特别是Quicksort,几乎不需要额外的空间,并且具有良好的缓存局部性,因此在许多情况下,它比合并排序要快。 此外,这是非常容易的O通过枢轴适当选择几乎完全避免快速排序的最坏情况下的运行时间 2) -如随机挑选它(这是一个很好的策略)。 实际上,quicksort的许多现代实现(尤其是libstdc ++的std::sort )实际上都是内省型,其理论上最坏的情况是O( log ),与合并排序相同。 它通过限制递归深度并在超过log 切换到其他算法(堆排序)来实现此目的。 回答2 正如许多人所指出的,Quicksort的平均案例性能要比mergesort更快。
  • 数据结构与算法总结笔记 及其 Python代码实现
    常用tips 常用的数据结构: 数组,链表,栈、队列、散列表、二叉树、堆、跳表、图、Trie 树; 常用的算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 ps: 以下的笔记摘抄整理自极客时间,侵删 常见的时间复杂度: 常见的空间复杂度: O(1)、O(n)、O(n2) (表示算法的存储空间与数据规模之间的增长关系) 数据结构相关 1 数组: 组用一块连续的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但插入、删除操作也因此变得比较低效,平均情况时间复杂度为 O(n) 2 链表 链表不同于数组,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用。 缓存淘汰策略 常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used) 三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。 单链表: 头结点用来记录链表的基地址,可以根据头结点来遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。 循环链表: 循环链表是一种特殊的单链表。跟单链表唯一的区别就在尾结点
  • 快速排序分区方法的稳定性(Stability of quicksort partitioning approach)
    问题 以下Quicksort分区算法是否能产生稳定的排序(即它是否以相等的值保持元素的相对位置): partition(A,p,r) { x=A[r]; i=p-1; for j=p to r-1 if(A[j]<=x) i++; exchange(A[i],A[j]) exchang(A[i+1],A[r]); return i+1; } 回答1 在一种情况下,您的分区算法将进行交换,这将更改相等值的顺序。 这是一张图像,可帮助演示您的就地分区算法如何工作: 我们使用j索引遍历每个值,如果看到的值小于分区值,则通过将其与紧靠浅灰色子数组右边的元素交换,将其附加到浅灰色子数组中。 浅灰色子数组包含所有<=分区值的元素。 现在,让我们看一下(c)阶段,并考虑以下情况:白色区域的开头是三个9,然后是1。也就是说,我们要检查9是否等于分区值。 。 我们看一下前9个,发现它不是<= 4,因此我们将其保留在原位,然后将j向前移动。 我们查看下一个9,发现它不是<= 4,因此我们也将其保留在原处,然后将j向前移动。 我们还将第三个9保留在原位。 现在我们看一下1,它小于分区,因此我们将其与前9交换。然后要完成算法,我们将分区值与i + 1的值(即第二个9)交换。现在,我们已经完成了分区算法,而原来本来是第三的9则是第一。 回答2 如果您愿意添加第二个键,则任何排序都可以转换为稳定排序。
  • linux C/C++服务器后台开发面试题总结(算法和数据结构篇)
    1.给定一个单向链表(长度未知),请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法,并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的:当m=0时,链表的最后一个元素将被返回。 解决问题方法思路如下: 方法一:如果我们知道链表的长度n,查找倒数第m个元素,也就是查找正序的第(n - m)个元素(这里的序号只是为了分析,可能跟题目不一定正确的符合)。那么这样来说就简单很多。首先遍历链表得到链表长度,然后重新遍历一次,查找正数第(n-m)个元素。时间复杂度大约是O(2n)。 方法二:我们是不是可以提供一个辅助存储空间,是的我们在遍历到链表结束的时候可以回溯到倒数第m个元素。比如用一个支持随机访问的容器记录链表每一个节点的地址。那么这样的就可以只遍历一次链表就能得到结果。时间复杂度大约是O(n),但是我们是用空间换取时间的,辅助存储空间的大小由m决定,如果m过大也是不可取的。 方法三:头结点指针为当前指针,尾节点指针为拖后指针。开始的时候当前指针和拖后指针初始化为链表的头结点,首先我们让当前指针遍历到第m个元素,拖后指针不变;然后同步更新当前指针和拖后指针;直到当前指针为链表结尾。这样我们就能保证当前指针和拖尾指针之间的距离是m。 代码如下: Node* FindMToLastNode(Node* pHead, int m) { //
  • 在 C 中对链表进行排序(Sorting a linked list in C)
    问题 我试图通过查找最大值,从其位置删除它,然后将其插入列表顶部来对链表进行排序。 我遇到的困难是在顶部实际删除和插入。 问题似乎出在 sortList 函数中包含的 while 循环中的 if 条件中,但我不确定如何修复它。 任何帮助,将不胜感激。 #include <stdio.h> #include <stdlib.h> typedef struct node{ int num; struct node *next; } Node, *NodePtr; void printList(NodePtr np); NodePtr makeList(void); NodePtr makeNode(int n); NodePtr sortList(NodePtr list); int main(void) { NodePtr list; printf("Enter numbers for the list (0 to end)\n"); list = makeList(); printList(list); list = sortList(list); printList(list); return 0; } NodePtr makeList(void) { NodePtr makeNode(int), np, top, last; int n; top = NULL; if
  • 计算机考研复试之数据结构
    博主本人整理资料不易,如果文章对大家有用的话,恳请大家能够动动小手帮忙点个赞,如果能点个关注的话那就更好了… 文章目录 数组和链表请你说一下红黑树和AVL树的定义、特点、以及二者的区别请你说一下哈夫曼编码请你介绍一下B+树请说一说你理解的栈溢出,并举个简单例子导致栈溢出请你回答一下堆和栈的区别,以及为什么栈要快请说说小根堆特点请回答一下Array和List,数组和链表的区别请问求第k大的数的方法及各自的复杂度是怎样的,另外当有相同元素时,还可以使用什么不同的方法求第k大的元素请你来介绍一下各种排序算法及时间复杂度请你介绍一下快速排序算法;以及什么是稳定性排序,快速排序是稳定的吗;请你说一说哈希冲突的解决方法判断一个链表是否为回文链表,说出你的思路并手写代码递归的三要素普利姆算法克鲁斯卡尔算法二分查找冒泡排序 数组和链表 数组: 特点: 1.在内存中,数组是一块连续的区域 2.数组需要预留空间 在使用前需要提前申请所占内存的大小,这样不知道需要多大的空间,就预先申请可能会浪费内存空间,即数组空间利用率低 3.在数组起始位置处,插入数据和删除数据效率低 4.随机访问效率很高,时间复杂度可以达到O(1) 5.数组开辟的空间,在不够使用的时候需要扩容,扩容的话,就会涉及到需要把旧数组中的所有元素向新数组中搬移 6.数组的空间是从栈分配的 优点: 随机访问性强,查找速度快,时间复杂度为O(1
  • 将数字插入排序的数字数组的有效方法?(Efficient way to insert a number into a sorted array of numbers?)
    问题 我有一个已排序的JavaScript数组,并且想在该数组中再插入一个项目,以使结果数组保持排序状态。 我当然可以实现一个简单的quicksort样式的插入函数: var array = [1,2,3,4,5,6,7,8,9]; var element = 3.5; function insert(element, array) { array.splice(locationOf(element, array) + 1, 0, element); return array; } function locationOf(element, array, start, end) { start = start || 0; end = end || array.length; var pivot = parseInt(start + (end - start) / 2, 10); if (end-start <= 1 || array[pivot] === element) return pivot; if (array[pivot] < element) { return locationOf(element, array, pivot, end); } else { return locationOf(element, array, start, pivot); } }
  • 数据结构与算法概述一:算法复杂度(空间与时间)、数组、链表、队列、算法(递归、排序、冒泡、插入、选择、归并、快速、桶排序、散列表)
    1.定义 1.数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。 2.数据结构是为算法服务的,算法是要作用在特定的数据结构上的。 3.最常用的数据结构:数组、链表、栈、队列、散列表、二叉树‘、堆、跳表、图、Tire树 4.常用的算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 2.算法复杂度(时间与空间) 1.大O复杂度表示法 T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。 公式中的O,表示,代码的执行时间T(n)与f(n)表达式成正比。 大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。 第一个例子中的T(n) = O(2n+2),第二个例子中的T(m) = 0(2n2 +2n+3)。当n很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。只需要记录最大量级就可以了,用大O表示法表示,两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。 2.复杂度分析法则 1)单段代码看高频:比如循环。 2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。 3
  • 【09】排序(下):如何用快排思想在O(n)内查找第K大元素?
    09 排序(下):如何用快排思想在O(n)内查找第K大元素? 1. 分治思想2. 归并排序3. 快速排序4. 归并排序与快速排序的区别5. 思考6. 参考资料7. 声明 1. 分治思想 分治思想:分治,顾明思意,就是分而治之,将一个大问题分解成小的子问题来解决,小的子问题解决了,大问题也就解决了。分治与递归的区别:分治算法一般都用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。 2. 归并排序 算法原理 先把数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两部分合并到一起,这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢?写递归代码的技巧就是先写出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。递推公式怎么写?如下 递推公式:merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件:p >= r 不用再继续分解代码实现 def merge_sort(collection): """归并排序""" length = len(collection) if length > 1: # 递归法完成第一步划分子表 midpoint = length // 2 # 向下取整 left_half = merge_sort(collection[
  • 使用Python进行快速排序(Quicksort with Python)
    问题 我对python完全陌生,我正在尝试在其中实现quicksort。 有人可以帮我完成我的代码吗? 我不知道如何连接三个数组并打印它们。 def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) sort(less) sort(pivot) sort(greater) 回答1 def sort(array=[12,4,5,6,7,3,1,15]): """Sort the array by using quicksort.""" less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) elif x == pivot: equal.append(x) elif x > pivot: greater.append(x) # Don't
  • 快速分类最坏的情况(Quick sort Worst case)
    问题 我正在研究以下仅需要的程序,以便更好地理解它。 Quicksort在最坏情况下的运行时间是多少?什么情况下可能导致此性能下降? 我们如何修改quicksort程序以减轻此问题? 我知道它的最坏情况为O(n^2)并且我知道它在枢轴唯一的最小或最大元素时发生。 我的问题是如何修改程序以减轻此问题。 一个好的算法将是好的。 回答1 Quicksort的性能取决于您的数据透视选择算法。 最幼稚的枢轴选择算法是只选择第一个元素作为枢轴。 很容易看到,如果您的数据已经排序,这将导致最坏的情况(第一个元素始终是最小值)。 有两种常见的算法可以解决此问题:随机选择一个枢轴,或选择三个的中位数。 随机是显而易见的,因此我将不做详细介绍。 三个中位数涉及选择三个元素(通常是第一个,中间和最后一个元素),然后选择这些元素的中位数作为枢轴。 由于随机数生成器通常是伪随机的(因此是确定性的),并且三个算法的非随机中值是确定性的,因此有可能构造导致最坏情况行为的数据,但是在正常使用中很少出现这种情况。 您还需要考虑性能影响。 您的随机数生成器的运行时间将影响快速排序的运行时间。 中位数为3,您正在增加比较的数量。 回答2 最差的性能条件: 当每次选择的枢轴是“最大”或“最小”时,此模式就会重复 所以1 3 5 4 2 如果按顺序依次选择1,2,3,4,5或5,4,3,2,1 那么最差的运行时间是O(n
  • topk问题的一些整理
    关于topk问题 1. 针对一堆杂乱无章的数,如何找中位数?2. 求最小的k个数(topk 问题)的两个解法及优劣比较  方法一:堆  方法二:快排变形 3. topk问题整理4. 这一堆数是数据流的形式给你的,而且后续可能还有新的数来加入,这个怎么做?代码的时间复杂度和算法该如何选择 1. 针对一堆杂乱无章的数,如何找中位数?   找中位数是不需要排序的; 找中位数本质就是找 topk 的问题,就按照 topk 问题的思路来解决就好了。   所以这个问题,直接来求解就是 求这堆数的第K个最大元素,K =? 。 已知nums n = len(nums) if n % 2 == 1: k = (n + 1) // 2 else: # 偶数的情况需要求第k-1和k大的元素,之后求平均值才是中位数 k = (n + 2) // 2 还有一道被考过的力扣题目:4.两个正序数组的中位数 2. 求最小的k个数(topk 问题)的两个解法及优劣比较 Top K 的两种经典解法(堆/快排变形)与优劣比较:   方法一:堆     堆的性质是每次可以找出最大或最小的元素。     在Python3中优先队列用堆(heapq)来表示,是一个小顶堆,(如果要每次找最大的值,可以把元素加负号,输出的值再去掉负号就是最大值)     如果要求最小的k个数,那么就可以维护一个大小为k的大顶堆
  • 牛客top算法题总结
    每日一刷的那些算法题(python) 反转链表最小的K个数二叉树的镜像旋转数组的最小数字快速排序冒泡排序选择排序 反转链表 题目要求: 输入一个链表,反转链表后,输出新链表的表头。 先上过程图: 举个栗子,这是↑最开始的链表 然后定义两个指针,一个名为pre,一个名为cur,另pre指向空,cur指向头结点pHead 当cur不为空时 ①将cur.next赋值给tmp结点,然后将pre的值赋值给cur.next; ②将cur赋值给pre,将tmp赋值给cur。 接下来就是以cur不为空为条件,一直循环此过程。 最后上代码: # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if pHead == None or pHead.next == None: return pHead cur = pHead pre = None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre 最小的K个数
  • 双向链表上的快速排序(QuickSort on Doubly Linked List)
    问题 我想在同步双向链表上实现 QuickSort 算法。 我给函数“分区”左右边框,然后它开始在左侧搜索较低的值,并将较大的值放在右侧。 这是有效的,因为我的枢轴元素始终是最正确的元素,并且在此步骤之后它位于中间。 我总是无限循环,我不知道为什么? 也许错误的中止条件? 她我的代码: private void quickSortRec(DoublyLinkedList in, ListElement l, ListElement r) { ListElement pivot = partition(in, l, r); if(pivot!=null && l!=r){ quickSortRec(in, in.first, pivot.prev); quickSortRec(in, pivot.next, in.first.prev); } } public ListElement partition(DoublyLinkedList in, ListElement l, ListElement r){ ListElement pivot = r; ListElement walker = l; if(l!=r){ while(walker != pivot){ if(walker.getKey() >= pivot.getKey()){ System.out.println
  • 算法设计与分析:深入理解快速排序
    文章目录 前言快速排序原理时间复杂度快速排序的pivot选择普通快速排序实现代码 总结 本文参考UCAS卜东波老师的计算机算法设计分析课程完成 前言 快速排序是复杂度 O ( n l o g n ) O(nlogn) O(nlogn)的排序算法中最常用的一个,也是分治思想的一个具体应用,关于分治思想的理解可以参考我的这篇文章分治思想。在了解快速排序前,我建议先理解分治思想和归并排序,掌握之后再来看快速排序,会有更好的效果。 快速排序 原理 快速排序与归并排序最明显的不同点是,前者基于数值划分,后者基于下标划分。快速排序会从数组中找一个中间数pivot,将数组小于piovt的放到左边,大于pivot的放到右边。这个貌似很容易理解(先不管pivot如何选取),我们可以得到如下伪代码: quick_sort(A): S_l = [],S_r = [] # s_l存储小于pivot的值,s_r存储大于pivot的值 choose pivot A[p] # 随机抽取 for i = 0 to |A|-1: if A[i] < A[p]: S_l += A[i] # 若比pivot小,则将A[i]放到pivot左边 else: S_r += A[i] # 否则将A[i]放到pivot右边 quick_sort(S-) quick_sort(S+) output S-,A[p],S+ #
  • 《算法图解》学习笔记(四):分而治之和快速排序(附代码)
    欢迎关注WX公众号:【程序员管小亮】 python学习之路 - 从入门到精通到大师 文章目录 欢迎关注WX公众号:【程序员管小亮】[python学习之路 - 从入门到精通到大师](https://blog.csdn.net/TeFuirnever/article/details/90017382)一、分而治之1)例子一2)例子二 二、快速排序三、再谈大O 表示法1)比较合并排序和快速排序2)平均情况和最糟情况 四、总结参考文章 一、分而治之 《算法图解》学习笔记(三):递归和栈(附代码) 深入介绍了递归。我们将探索 分而治之(divide and conquer,D&C) —— 一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供使用的工具。面对新问题时,你不再束手无策,而是自问:“使用分而治之能解决吗?” D&C好像很不错,那我们就一直用这个方法好了,然而它并不那么容易掌握,先来看示例。 1)例子一 假设你是农场主,有一小块土地(其实面积也不小了,168 x 64 = 10752 m 2 m^2 m2)。 你要将这块地均匀地分成方块,且分出的方块要尽可能大。一共有下面三种方法: 显然,上面的分法都不符合要求。那么如何将一块地均匀地分成方块,并确保分出的方块是最大的呢? 答案是使用D&C策略!D&C算法是递归的。使用D
  • 数据结构错题本
    目录 1.二分/折半查找 2.对称矩阵下标 3.根据前序确定可能中序 4.已知前序&后序 5.折半查找&二叉排序树 6.hash哈希 附:散列表的查找效率 处理冲突方法: 7.××与初始序列无关 8.顺序表插入/删除平均移动个数 9.中缀转后缀表达式 变种题:中转后缀的堆栈题 10.后缀求表达式值 11.满k叉树性质 12.WPL带权路径长度 13.AVL旋转 典例1 14.AVL树查找 15.双端队列 16.Prim 17.二维数组求地址题 18.AOE网 19.森林转成二叉树 20.树的存储 21.树性质 22.DFS和BFS生成树 23.快速排序 24.图&树的概念 25.Dijkstra 26.DFS和BFS(邻接表) 27.线索二叉树 28.拓扑&邻阵 29.B-树&B+树 30.B树的add 31.B树的del 32.del后add型题 (1)二叉排序树 (2)平衡二叉树 (3)折半查找树 33.二路归并算法 34.栈 35.递归求WPL 二叉树(二叉链表存储) 36.KMP算法 一.求next数组 二.匹配过程考察 37.哈夫曼树 38.归并的比较次数 39.表达式的min顶点数 39.堆栈 40.森林&树&BT遍历 41. 1.二分/折半查找 二分基本的查询下标的方法为(首下标+尾下标)/2,如果该下标非查询值,要剔除后在左边或右边继续循环。记住:把已经查询的值剔除
  • Python快速排序和冒泡排序(更新中)
    冒泡排序:第1次选出最大的数字,第2次选出 第二大的数字,以此类推,直到全部按大小排列完毕 冒泡排序比较次数(复杂度):c=n/2[(n-1)+0]=0.5(n^2-n) #复杂度是O(n²)—“n的平方级”* 快速排序:第1次随机挑选一个数,称为枢值,接下来,将所有要排序的数字分成两部分,第一部分是大于等于枢值的,第二部分是小于枢值的;从上面得到的2堆数字,分别采用第一步的方法各自再找一个枢值,也用同样的方法各分成2组;再对这4堆数字分别采用第一步的方法各自再找一个枢值,也用同样的方法各分成2组…四堆变八堆,八堆变十六堆,很快所有的数字就排好序了。 快速排序平均比较次数(复杂度):复杂度是O(n*log2[n])—以2为底,n的对数 快速排序最佳比较次数(复杂度):复杂度是O(n*log2[n])—以2为底,n的对数 快速排序最差比较次数(复杂度):复杂度是O(n²)—“n的平方级”(每次都恰好取到极值,退化为冒泡排序) 随着数据量变大,两种排序的运算次数(效率)的数量级差距会越来越大,同样配置的计算机,采用不同的算法,对一个超级大的数组/元组/数列等就行排序。使用快速排序算法的计算机1秒能完成的计算,若是使用冒泡排序可能需要运算到宇宙毁灭都算不完。 Python代码分别实现 冒泡排序: 快速排序: 直接调用列表类的sort方法快速实现: to be continued… 来源
  • 数据结构之排序心得
    算法的稳定性:如果待排序的两个元素Ri,Rj,其对应的关键字keyi=keyj,且在排序前Ri在Rj的前面,如果排序后Ri还在Rj的前面,则称这种排序算法是稳定的,否则称排序算法是不稳定的。内部排序和外部排序:内部排序是指在排序期间,元素全部存放在内存中的排序。外部排序是指排序期间元素无法全部同时存放在内存中,必须在排序过程中根据要求不断地在内外存之间移动的排序。1.插入排序1)插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。void InsertSort(ElemType A[], int n) { int i, j; for (i = 2; i <= n; i++) //依此将A[2]~A[n]插入到前面已排序序列 if (A[i].key < A[i - 1].key) //若A[i]的关键码小于其前驱,须将A[i]插入有序表 { A[0] = A[i]; //复制为哨兵 for (j = i - 1; A[0].key < A[j].key; --j) //从后往前查找待插入位置 A[j+1]=A[j]; //向后拖动 A[j+1]=A[0]; //复制到插入位置 } }时间复杂度:O(n2),空间复杂度:O(1).稳定性:稳定的排序方法。2)希尔排序:将待排序表分割成若个形如L[i,i+d,i+2d,i+3d,…i
  • 考研数据结构复试题目整理
    数据结构复试题目自整理 说复试题目过于牵强,只是自己整理的一些知识点而已,为了便于理解和背诵,有些部分定义和说明尽量简明扼要,如有错误请多多指教!(不可转载) 只涉及简答形式,代码未总结(有用点点赞啊啊我升到3级就可以自定义标签了谢谢~) 1.大O什么意思? 在时间复杂度中,一个算法中所有语句被重复执行的次数记为T(n),时间复杂度用来分析T(n)的数量级,也就是算法中基本语句被执行的次数,O的含义就是表示基本语句的数量级也就是算法的数量级。 在空间复杂度中,同样用O来表示基本运算所耗费的存储空间。 2.简述数据结构的三要素 逻辑结构:从逻辑上描述数据,即数据之间的逻辑关系。(线性结构和非线性结构) 物理结构:数据在计算机内的存储方式(顺序存储,链式存储,索引存储,散列存储) 数据的运算:数据的运算包括数据的定义与实现,运算的定义是针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。 3.循环比递归效率高吗? 并不能绝对的说循环比递归效率高。 递归的优点是:代码简洁清晰,容易检查代码的正确性。缺点是:当递归调用的次数很多时,对执行效率会有一定的影响。 循环的优点是:结构简单,速度快;缺点是:并不能解决所有问题,有些问题适合用递归来解决而不适合用循环。 4.简述各存储结构 顺序存储:采用一组连续的存储空间存储数据。 优点:简单,可以实现随机存取