Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Sorting Algorithm (1) Quick Sort C ++ implementation     - Camera-based face recognition OpenCV crawl and storage format (Python) (Linux)

- iTerm - let your command line can also be colorful (Linux)

- The most common and most effective security settings under linux (Linux)

- Java programmers talk about those advanced knowledge and direction (Programming)

- Ubuntu 14.04 to install file editor KKEdit 0.1.5 version (Linux)

- DRBD rapid installation and deployment (Server)

- Installation Yarock 1.1.4 Music Player in Ubuntu (Linux)

- Java synchronization mechanism used in locking Thought (Programming)

- Linux system started to learn: Teaches you install Fedora 22 on VirtualBox (Linux)

- Fedora10 use Git version Configuration Management (Linux)

- Docker use Dockerfile created since the launch of the service support SSH container mirror (Server)

- CentOS7 installation performance monitoring system (Server)

- C # how to generate a folder or file automatically rename (Programming)

- Linux System Getting Started Learning: install software packages on Ubuntu and Fedora (Linux)

- Linux operating system ARP Spoofing Defense (Linux)

- Java keyword final, static (Programming)

- Linux package management operations Basic entry (Linux)

- PostgreSQL transaction model introduction (Database)

- VirtualBox installation enhancements let the mouse move and share CentOS 6.4 (Linux)

- Linux shell script debugging (Linux)

 
         
  Sorting Algorithm (1) Quick Sort C ++ implementation
     
  Add Date : 2018-11-21      
         
         
         
  Quick Sort Basic Features

Time complexity: O (n * lgn)
The worst: O (n ^ 2)
Space complexity: best case: O (lgn), worst case: O (n), average case: O (lgn)
Unstable.

Fast sorting Since each recursion takes up one space to return to the median position, the space complexity of one recursion is O (1).

The recursion depth for the best case and the average case is O (lgn), and the corresponding spatial complexity is O (lgn)

The worst-case recursion depth is O (n), and the space complexity is O (n).

algorithm

QUICKSORT (A, p, r)
    If p < r
       Then q PARTITION (A, p, r) // key
            QUICKSORT (A, p, q - 1)
            QUICKSORT (A, q + 1, r)
 
PARTITION (A, p, r)
      X <-- A [r]
      I <-- p - 1
      For j <-- p to r - 1
           Do if A [j] < x
                 Then i <-- i + 1
                     Exchange A [i] < -> A [j]
      Exchange A [i + 1] < -> A [r]
      Return i + 1

Source code

Class declaration

Class BaseSort {
Public:
    BaseSort () {}
    Virtual void sort () = 0;
};
 
Class QuickSort: public BaseSort {
Public:
    QuickSort (int Array [], int len): BaseSort () {
        This-> Array = Array;
        This-> len = len;
    }}
    Void sort ();
Private:
    Int partition (int Array [], int start, int end);
    Void quicksort (int Array [], int start, int end);
Private:
    Int * Array;
    Int len;
};
 

The relevant member functions are implemented

Void QuickSort :: sort () {
    Quicksort (Array, 0, len-1);
}}
Void QuickSort :: quicksort (int Array [], int start, int end) {
    If (start < end) {
        Int mid = this-> partition (Array, start, end);
        If (start < mid - 1)
            Quicksort (Array, start, mid-1);
        If (mid + 1 < end)
            Quicksort (Array, mid + 1, end);
    }}
}}
Int QuickSort :: partition (int Array [], int start, int end) {
    Int i, j, x, tmp;
    X = Array [end];
    I = start -1;
    
    For (j = start; j < end; j ++) {
        If (Array [j] < = x) {
            I ++;
            Tmp = Array [j];
            Array [j] = Array [i];
            Array [i] = tmp;
        }}
    }}
    
    Tmp = Array [end];
    Array [end] = Array [i + 1];
    Array [i + 1] = tmp;
    If (DEBUG) {
        PrintArray (Array, len, "MidResult");
    }}
    Return i + 1;
}}
test:

Int a [10] = {7,3,2,9,8,5,1,10,4,6};
Int len = 10;
 
QuickSort * quicksort = new QuickSort (a, len);
Quicksort-> sort ();
PrintArray (a, len, "QuickSort");
     
         
         
         
  More:      
 
- Installation of network monitoring ntopng under CentOS 6.4 (Linux)
- Linux disk management practices (Linux)
- CentOS6.3 build a Python 3.3 environment to access Oracle 11gR2 (Database)
- linux smartd [FAILED] appears at startup (Linux)
- GNU / Linux system, how to clean up memory space (Linux)
- Recycle Bin function realization in Linux (Linux)
- Linux Getting Started Tutorial: / var / spool / clientmqueue fill the root directory (Linux)
- Oracle to read and modify the data block process (Database)
- jdbc Oracle database connection string writing pluggable (Database)
- Linux formatted partition error Could not stat / dev / sda No such file or directory Solution (Linux)
- Spring loaded container finishes executing a method (Programming)
- Scope of variables in Object-C (Programming)
- Single-node Hadoop environment to build (Server)
- Find details block device with Linux blkid command (Linux)
- MySQL stored procedures and triggers (Database)
- How to enhance the Nagios server security (Linux)
- Three binary tree traversal (recursive, non-recursive traversal and Morris) (Programming)
- Android Custom View step (Programming)
- Install Web-based monitoring tool: Linux-Dash (Server)
- Sublime Text 3 shortcuts summary (Linux)
     
           
     
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.