双向链表上的快速排序

2024年8月28日 | 阅读 18 分钟

在为双向链表实现快速排序之前，让我们先了解一下快速排序。快速排序是另一种使用分治法实现的排序算法。由于其在平均情况下的高性能（n log n），快速排序也是一种有用的排序算法选项。与归并排序不同，快速排序在排序过程中不使用额外的数组，虽然其平均情况与归并排序相同，但在快速排序的情况下，(n log n) 的隐藏因子通常更低。

快速排序首先选择一个枢轴，然后围绕它对数组进行分区。所有小于枢轴的项放在一边，而所有大于枢轴的元素放在另一边。这个分区过程对较小的子数组重复进行，从而得到一个已排序的数组。选择枢轴是分区的第一步。在我们的算法中，我们将始终使用数组的最后一个成员作为枢轴，我们将专注于快速排序的概念。枢轴可以通过多种方式选择，包括元素的中间值、数组中的第一个成员、随机元素等。

在选择枢轴之后，我们必须将所有小于枢轴的元素放在一边，所有大于枢轴的元素放在另一边。我们将通过遍历数组并什么也不做来实现这一点。

如果我们遇到一个大于枢轴的元素，那么将形成一个大于枢轴的元素簇。
现在，任何小于枢轴的元素都将与较大元素簇的第一个元素交换。
因此，我们将创建另一个小于枢轴的元素簇。
最后，我们将枢轴与较大元素簇中的第一个成员交换。

C++ 代码

现在让我们编写代码，借助快速排序算法对双向链表数据结构执行排序操作。首先，让我们编写一个 C++ 代码来对双向链表数据结构执行快速排序。

// A C++ program to sort a linked list using Quicksort  
#include <bits/stdc++.h> 
using namespace std; 
  
/* a node of the doubly linked list */
class Node  
{  
    public: 
    int data;  
    Node *next;  
    Node *prev;  
};  
  
/* A utility function to swap two elements */
void swap ( int* a, int* b )  
{ int t = *a; *a = *b; *b = t; }  
  
// A utility function to find 
// last node of linked list  
Node *lastNode(Node *root)  
{  
    while (root && root->next)  
        root = root->next;  
    return root;  
}  
  
/* Considers the last element as pivot,  
places the pivot element at its  
correct position in a sorted array,  
and places all smaller (smaller than  
pivot) to the left of the pivot and all greater 
elements to right of pivot */
Node* partition(Node *l, Node *h)  
{  
    // set pivot as h element  
    int x = h->data;  
  
    // similar to i = l-1 for array implementation  
    Node *i = l->prev;  
  
    // Similar to "for (int j = l; j <= h- 1; j++)"  
    for (Node *j = l; j != h; j = j->next)  
    {  
        if (j->data <= x)  
        {  
            // Similar to i++ for array  
            i = (i == NULL)? l : i->next;  
  
            swap(&(i->data), &(j->data));  
        }  
    }  
    i = (i == NULL)? l : i->next; // Similar to i++  
    swap(&(i->data), &(h->data));  
    return i;  
}  
  
/* A recursive implementation  
of quicksort for linked list */
void _quickSort(Node* l, Node *h)  
{  
    if (h != NULL && l != h && l != h->next)  
    {  
        Node *p = partition(l, h);  
        _quickSort(l, p->prev);  
        _quickSort(p->next, h);  
    }  
}  
  
// The main function to sort a linked list. 
// It mainly calls _quickSort()  
void quickSort(Node *head)  
{  
    // Find last node  
    Node *h = lastNode(head);  
  
    // Call the recursive QuickSort  
    _quickSort(head, h);  
}  
  
// A utility function to print contents of arr  
void printList(Node *head)  
{  
    while (head)  
    {  
        cout << head->data << " ";  
        head = head->next;  
    }  
    cout << endl;  
}  
  
/* Function to insert a node at the  
beginning of the Doubly Linked List */
void push(Node** head_ref, int new_data)  
{  
    Node* new_node = new Node; /* allocate node */
    new_node->data = new_data;  
  
    /* since we are adding at the 
    begining, prev is always NULL */
    new_node->prev = NULL;  
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);  
  
    /* change prev of head node to new node */
    if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;  
  
    /* move the head to point to the new node */
    (*head_ref) = new_node;  
}  
  
/* Driver code */
int main()  
{  
    Node *a = NULL;  
    int data;
    char ch;
        /*  Perform tree operations  */
        do    
        {
            cout<<"\nSelect one of the operations::"<<endl;
            cout<<"1. To insert a new node in the Doubly Linked List."<<endl;
            cout<<"2. To display the nodes of the Doubly Linked List."<<endl;
            cout<<"3. To perform Quicksort on the Doubly Linked List."<<endl;
             
            int choice;
            cin>>choice;            
            switch (choice)
            {
            case 1 : 
                cout<<"Enter the value of the node to be inserted"<<endl;
                cin>>data;
                push(&a,data);                     
                break;                          
            case 2 : 
                cout<<"Contents of the Doubly Linked List are::"<<endl;
                printList(a);
                break; 
            case 3 : 
                cout<<"Quicksort applied sucessfully on the Doubly Linked List."<<endl;
                quickSort(a);
                break;
            default : 
                cout<<"Wrong Entry \n ";
                break;   
            }
 
            cout<<"\nDo you want to continue (Type y or n) \n";
            cin>>ch;                        
        } while (ch == 'Y'|| ch == 'y');
    return 0;  
}  // end of main function

输出

上述代码给出以下输出。

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter the value of the node to be inserted
20

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter the value of the node to be inserted
30

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1 
Enter the value of the node to be inserted
12

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter the value of the node to be inserted
3

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1 
Enter the value of the node to be inserted
77

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter the value of the node to be inserted
54

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2
Contents of the Doubly Linked List are::
54 77 3 12 30 20 

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
3
Quicksort applied successfully on the Doubly Linked List.

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2
Contents of the Doubly Linked List are::
3 12 20 30 54 77 

Do you want to continue (Type y or n) 
n

通过这种方式，我们编写了一个 C++ 代码来对双向链表数据结构执行快速排序操作。为双向链表数据结构编写了三个函数，一个是向双向链表添加新节点，第二个是显示双向链表的所有节点并显示与这些节点关联的值，第三个函数是对双向链表数据结构执行快速排序操作。

用户首先在双向链表数据结构中添加足够数量的节点。节点成功添加后，通过从每次操作后显示的菜单中选择第三个选项，对双向链表数据结构执行快速排序操作，这将调用代码中编写的 Quicksort () 函数，并将双向链表的根节点作为参数传递。

完成快速排序操作后，用户可以通过选择用户的第二个选项来显示双向链表中节点的值，从而确认快速排序操作的结果。所有操作完成后，用户可以通过输入“n”或“N”字符退出代码。

Java 代码

让我们编写一个 Java 代码来对双向链表数据结构执行快速排序。

// A Java program to sort a linked list using Quicksort 

import java.util.Scanner;

class QuickSort_using_Doubly_LinkedList{ 
    Node head; 
    
/* a node of the doubly linked list */  
    static class Node{ 
        private int data; 
        private Node next; 
        private Node prev; 
          
        Node(int d){ 
            data = d; 
            next = null; 
            prev = null; 
        } 
    } 
      
// A utility function to find last node of linked list     
    Node lastNode(Node node){ 
        while(node.next!=null) 
            node = node.next; 
        return node; 
    } 
      
  
/* Considers the last element as pivot, places the pivot element at its 
   correct position in a sorted array, and places all smaller (smaller than 
   pivot) to the left of the pivot and all greater elements to right of pivot */
    Node partition(Node l, Node h) 
    { 
       // set pivot as h element 
        int x = h.data; 
          
        // similar to i = l-1 for array implementation 
        Node i = l.prev; 
          
        // Similar to "for (int j = l; j <= h- 1; j++)" 
        for(Node j=l; j!=h; j=j.next) 
        { 
            if(j.data <= x) 
            { 
                // Similar to i++ for array 
                i = (i==null) ? l : i.next; 
                int temp = i.data; 
                i.data = j.data; 
                j.data = temp; 
            } 
        } 
        i = (i==null) ? l : i.next;  // Similar to i++ 
        int temp = i.data; 
        i.data = h.data; 
        h.data = temp; 
        return i; 
    } 
      
    /* A recursive implementation of quicksort for linked list */
    void _quickSort(Node l,Node h) 
    { 
        if(h!=null && l!=h && l!=h.next){ 
            Node temp = partition(l,h); 
            _quickSort(l,temp.prev); 
            _quickSort(temp.next,h); 
        } 
    } 
      
    // The main function is to sort a linked list. It mainly calls _quickSort() 
    public void quickSort(Node node) 
    { 
        // Find last node 
        Node head = lastNode(node); 
          
        // Call the recursive QuickSort 
        _quickSort(node,head); 
    } 
      
     // A utility function to print contents of arr 
     public void printList(Node head) 
     { 
        while(head!=null){ 
            System.out.print(head.data+" "); 
            head = head.next; 
        } 
    } 
      
    /* Function to insert a node at the beginning of the Doubly Linked List */
    void push(int new_Data) 
    { 
        Node new_Node = new Node(new_Data);     /* allocate node */
          
        // if head is null, head = new_Node 
        if(head==null){ 
            head = new_Node; 
            return; 
        } 
          
        /* link the old list off the new node */
        new_Node.next = head; 
          
        /* change prev of head node to new node */
        head.prev = new_Node; 
          
        /* since we are adding at the begining, prev is always NULL */
        new_Node.prev = null; 
          
        /* move the head to point to the new node */
        head = new_Node; 
    } 
      
    /* Driver program to test above written function */
    public static void main(String[] args){ 
        QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList(); 
        Scanner scan = new Scanner(System.in);
        char ch;
        /**  Perform tree operations  **/
        do    
        {
            System.out.println("\nSelect one of the operations::\n");
            System.out.println("1. To insert a new node in the Doubly Linked List.");
            System.out.println("2. To display the nodes of the Doubly Linked List.");
            System.out.println("3. To perform Quicksort on the Doubly Linked List.");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                list.push(scan.nextInt());                     
                break;                          
            case 2 : 
                System.out.println("Doubly Linked List::");
                list.printList(list.head);
                break;                                          
            case 3 : 
                System.out.println("Quicksort done.");
                list.quickSort(list.head);
                break;     
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');
          
    } 
} 

输出

上述 Java 代码执行后会给出以下输出。

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
265

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
400 

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
133

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
879

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
228

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
609

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
551

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2
Doubly Linked List::
551 609 228 879 133 400 265 
Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1
Enter integer element to insert
23

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2
Doubly Linked List::
23 551 609 228 879 133 400 265 
Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
3
Quicksort done.

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2
Doubly Linked List::
23 133 228 265 400 551 609 879 
Do you want to continue (Type y or n) 

N

通过这种方式，我们编写了一个 Java 代码来对双向链表数据结构执行快速排序操作。为双向链表数据结构编写了三个函数，一个是向双向链表添加新节点，第二个是显示双向链表的所有节点并显示与这些节点关联的值，最后一个函数是对双向链表数据结构执行快速排序操作。

C 代码

让我们编写一个 C 代码来对双向链表数据结构执行快速排序。

// A C program to sort a linked list using Quicksort 
// #include <iostream> 
#include <stdio.h>
#include<stdlib.h>

// using namespace std; 
  
/* a node of the doubly linked list */
struct Node 
{ 
    int data; 
    struct Node *next; 
    struct Node *prev; 
}; 
  
typedef struct Node Node;

/* A utility function to swap two elements */
void swap ( int* a, int* b ) 
{   int t = *a;      *a = *b;       *b = t;   } 
  
// A utility function to find last node of linked list 
struct Node *lastNode(Node *root) 
{ 
    while (root && root->next) 
        root = root->next; 
    return root; 
} 
  
/* Considers the last element as pivot, places the pivot element at its 
   correct position in a sorted array, and places all smaller (smaller than 
   pivot) to the left of the pivot and all greater elements to right of pivot */
Node* partition(Node *l, Node *h) 
{ 
    // set pivot as h element 
    int x  = h->data; 
  
    // similar to i = l-1 for array implementation 
    Node *i = l->prev; 
  
    // Similar to "for (int j = l; j <= h- 1; j++)" 
    for (Node *j = l; j != h; j = j->next) 
    { 
        if (j->data <= x) 
        { 
            // Similar to i++ for array 
            i = (i == NULL)? l : i->next; 
  
            swap(&(i->data), &(j->data)); 
        } 
    } 
    i = (i == NULL)? l : i->next; // Similar to i++ 
    swap(&(i->data), &(h->data)); 
    return i; 
} 
  
/* A recursive implementation of quicksort for linked list */
void _quickSort(struct Node* l, struct Node *h) 
{ 
    if (h != NULL && l != h && l != h->next) 
    { 
        struct Node *p = partition(l, h); 
        _quickSort(l, p->prev); 
        _quickSort(p->next, h); 
    } 
} 
  
// The main function is to sort a linked list. It mainly calls _quickSort() 
void quickSort(struct Node *head) 
{ 
    // Find last node 
    struct Node *h = lastNode(head); 
  
    // Call the recursive QuickSort 
    _quickSort(head, h); 
} 
  
// A utility function to print contents of arr 
void printList(struct Node *head) 
{ 
    while (head) 
    { 
        printf("%d  ",head->data); 
        head = head->next; 
    } 
    printf("\n"); 
} 
  
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = malloc(sizeof(Node)); //new Node;     /* allocate node */
    new_node->data  = new_data; 
  
    /* since we are adding at the begining, prev is always NULL */
    new_node->prev = NULL; 
  
    /* link the old list off the new node */
    new_node->next = (*head_ref); 
  
    /* change prev of head node to new node */
    if ((*head_ref) !=  NULL)  (*head_ref)->prev = new_node ; 
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    struct Node *a = NULL; 
    int data;
    char ch;
        /*  Perform tree operations  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Doubly Linked List.");
            printf("\n2. To display the nodes of the Doubly Linked List.");
            printf("\n3. To perform Quicksort on the Doubly Linked List.\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value of the node to be inserted\n");
                scanf("%d",&data);
                push(&a,data);                     
                break;                          
            case 2 : 
                printf("\nContents of the Doubly Linked List are::\n");
                printList(a);
                break; 
            case 3 : 
                printf("\nQuicksort applied sucessfully on the Doubly Linked List.\n");
                quickSort(a);
                break;
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y');
  
    return 0; 
} 

输出

上述 C 代码会给出以下输出。

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1

Enter the value of the node to be inserted
11

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1

Enter the value of the node to be inserted
65

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1

Enter the value of the node to be inserted
32

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1

Enter the value of the node to be inserted
9 

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2

Contents of the Doubly Linked List are::
9  32  65  11  

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
1

Enter the value of the node to be inserted
522

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2

Contents of the Doubly Linked List are::
522  9  32  65  11  

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
3

Quicksort applied successfully on the Doubly Linked List.

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Quicksort on the Doubly Linked List.
2

Contents of the Doubly Linked List are::
9  11  32  65  522  

Do you want to continue (Type y or n)
n

通过这种方式，我们编写了一个 C 代码来对双向链表数据结构执行快速排序操作。为双向链表数据结构编写了三个函数，一个是向双向链表添加新节点，第二个是显示双向链表的所有节点并显示与这些节点关联的值，第三个函数是对双向链表数据结构执行快速排序操作。

下一主题逆序对计数

双向链表上的快速排序

C++ 代码

Java 代码

C 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

双向链表上的快速排序

C++ 代码

Java 代码

C 代码

相关帖子

冒泡排序和归并排序的区别

如果给出两种遍历序列，能否构建二叉树

对给定矩阵进行排序

将二叉树展平成链表

RSS 链表

克隆带有随机指针的二叉树

数据结构中的动态内存分配

字符串的有效分割数量

查找数组中左侧之和等于右侧之和的元素

排序大整数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器