- 2021-12-19 17:02
*views 2*- data structure

1. Concept of sorting

Sorting is to make a string of data compare according to a specific law , Perform the arranged operations .

Common sorting algorithms

// Interface of sorting implementation void InsertSort(int* a,int n); // Insert sort void ShellSort(int* a,int n);

// Shell Sort void SelectSort(int* a, int n); // Select sort void AdjustDwon(int* a, int n,

int root); void HeapSort(int* a, int n);// Heap sort // Bubble sort void BubbleSort(int* a,

int n) // Recursive implementation of quick sort // Quick sort hoare edition int PartSort1(int* a, int left, int right);

// Quick sequencing excavation method int PartSort2(int* a, int left, int right); // Quick sort before and after pointer method int

PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int

right); // Quick sort Non recursive implementation void QuickSortNonR(int* a, int left, int right) //

Recursive implementation of merge sort void MergeSort(int* a, int n) // Non recursive implementation of merge sort void MergeSortNonR(int* a,

int n) // Count sort void CountSort(int* a, int n)

2. Implementation of common sorting

1. Insert sort

Direct insertion

Direct insertion method is a simple insertion sorting method , Is to insert the elements to be sorted one by one into an ordered sequence that has been sorted , Form a new ordered sequence .

It's like {3,6,1,5} Insert into {2,4} in , obtain {1,2,3,4,5,6}.

How did it come about ?

Directly inserted properties

* 1. The closer the element is to order before insertion , The more efficient the insertion is

* 2. Time complexity ：O（N^2）

* 3. Spatial complexity ：O（1）

* 4. stability ： stable

Shell Sort （ Reduce incremental sort ）

Hill sort is to select an integer first , Divide the elements to be sorted into several groups , All those with equal distance are divided into the same group , And sort each group of elements .

Characteristics of Hill sort

* 1. Hill sort is an optimization of direct insertion sort

* 2.gap>1 Are pre sorted , The purpose is to make the sorting elements closer to order .

* 3. Time complexity ：O（N^1.3——N^2）

* 4. stability ： instable

2. Select sort

Select the smallest from the elements to be sorted each time （ maximum ） One of , Place at the beginning of the sequence , Until all elements are arranged .

Select Sorting directly

Direct selection is to compare the elements to be sorted , Choose the largest or smallest one , Then repeat this operation for the remaining elements , Until the remaining elements are 1, Stop operation .

Directly select the characteristics of sorting

* 1. Direct selection and sorting is easy to understand , But the efficiency is not very good , Rarely used in practice

* 2. Time complexity ：O（N^2）

* 3. Spatial complexity ：O（1）

* 4. stability ： instable

Heap sort

Heap sort is a sort algorithm designed by using the data structure heap , It is a kind of selective sorting . Remember to build a lot in ascending order , Build small piles in descending order .

Characteristics of heap sorting

* 1. Heap sort uses heap to select numbers , Much more efficient .

* 2. Time complexity ：O(N*logN)

* 3. Spatial complexity ：O(1)

* 4. stability ： instable

3. Exchange sort

Exchange the order of the two elements according to the comparison results of the two elements , Move the larger value to the tail , Smaller values move forward .

Bubble sort

Characteristics of bubble sorting

* 1. Bubble sort is a sort that is very easy to understand

* 2. Time complexity ：O(N^2)

* 3. Spatial complexity ：O(1)

* 4. stability ： stable

Quick sort

Fast sorting is a sort method of binary tree exchange , Take any element as the reference value , Then the set is divided into two sequences , Left less than right , Repeat as above .

Common ways to divide the interval into left and right halves according to the benchmark value are ：

* 1. hoare edition

* 2. Excavation method

* 3. Front and back pointer versions

4. Merge sort

Merge sort is to sort the existing subsequences , Merge two ordered tables into one ordered table .

Characteristics of merging and sorting

* 1. The disadvantage of merging is the need O(N) Spatial complexity of , The thinking of merging and sorting is more about solving the problem of external sorting in the disk .

* 2. Time complexity ：O(N*logN)

* 3. Spatial complexity ：O(N)

* 4. stability ： stable

5. Non comparative sort

Characteristics of non comparative sorting

* 1. When the count sort is in the data range set , Very efficient , However, the scope of application and scenarios are limited .

* 2. Time complexity ：O(MAX(N, Range ))

* 3. Spatial complexity ：O( Range )

* 4. stability ： stable

Technology

Daily Recommendation

views 5

views 3

©2019-2020 Toolsou All rights reserved,

Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms （java code ） use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?