Shulou(Shulou.com)06/01 Report--

Quick sort

Pick an element from the series, called "pivot", and reorder the series, with all elements smaller than the benchmark placed in front of the datum, and all elements larger than the datum behind the datum (the same number can be on either side). After the partition exits, the datum is in the middle of the series. This is called a partition operation. Recursive sorts the subseries of elements less than the reference value and the subseries of elements greater than the reference value.

Sort effect:

Cdn2.b0.upaiyun.com/2012/01/Visual-and-intuitive-feel-of-7-common-sorting-algorithms.gif ">

Int PartSort (int* a, int left, int right) / / sort of each step {int key = a [right]; int begin = left; int end = right-1; while (begin

< end) { while (begin < end && a[begin] = key) { --end; } if (begin < end) { swap(a[begin], a[end]); } } if (a[begin]>

A [right]) {swap (a [begin], a [right]); return begin;} else {return right;} void QuickSort (int* a, int left, int right) / / Quick sort {assert (a); if (left > = right) {return;} int div = PartSort (a, left, right); QuickSort (a, left, div-1) QuickSort (a, div + 1, right);}

two。 Heap sort:

Heap sorting (Heapsort) is a sort algorithm designed by using the data structure of heap. The heap is a structure similar to a complete binary tree and satisfies the heap property at the same time: that is, the key value or index of a child node is always less than (or greater than) its parent node.

Sort effect:

Void AdjustDown (int* atraining sizeyogt size,size_t parents) / / Dadu downregulation {assert (a); size_t child = parents * 2 + 1; while (child)

< size) { if (child + 1 < size && a[child + 1]>

A [child]) {+ + child;} if (a [child] > a [parents]) {swap (a [child], a [parents]); parents = child; child = parents * 2 + 1 } else {break;}} void HeapSort (int* a, size_t size) / / heap sort {assert (a); for (int I = (size-2) / 2; I > = 0; iMel -) / / build heap {AdjustDown (a, size, I);} for (int I = 0; I

< size; i++) { swap(a[0], a[size - i - 1]); AdjustDown(a, size - i-1, 0); }} 3.选择排序： 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。 效果如下： void SelectSort(int* a, size_t size) //选择排序{ assert(a); for (size_t i = 0; i < size; i++) { int* p = a; for (size_t j = 0; j < size-i; j++) { if (*p < a[j]) { p = &a[j]; } } swap(*p, a[size-i-1]); } } 4.冒泡排序： 冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。 效果如下： void BubbleSort(int* a,size_t size) //冒泡排序{ for (int i = 0; i < size; i++) { for (int j = 0; j < size - i - 1; j++) { if (a[j]>

A [j + 1]) {swap (a [j], a [j + 1]);}

5. Insert sort

Introduction:

The algorithm description of insert sorting (Insertion Sort) is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning the unsorted data from back to front in the sorted sequence, finding the corresponding position and inserting it. In the implementation of insertion sorting, in-place sorting is usually used (that is, only the extra space of O (1) is needed), so in the process of scanning from back to front, the sorted elements need to be moved backward step by step to provide insertion space for the latest elements.

Steps:

1. Starting with the first element, the element can be considered to have been sorted

two。 Take out the next element and scan from back to front in the sorted sequence of elements

3. If the element (sorted) is larger than the new element, move the element to the next location

4. Repeat step 3 until you find the location where the sorted element is less than or equal to the new element

5. Insert a new element into that location

6. Repeat step 2

Void InsertSort (int * a, size_t size) / / insert sort {assert (a); for (int I = 1; I

< size - 1; i++) { int end =i; int tmp = a[i]; while (end >

= 0 & a [end-1] > tmp) {a [end] = a [end-i];-- end;} a [end-1] = tmp;}}

6. Hill ranking

Introduction:

Hill sorting, also known as decreasing incremental sorting algorithm, is a high-speed and stable improved version of insertion sorting. Hill sorting is an improved method based on the following two properties of insertion sorting:

1. Insertion sorting is efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.

2. But insert sorting is generally inefficient because it can only move data one bit at a time

Sort effect:

Void ShellSort (int* a, size_t size) / / Hill sort {int gap = size; while (gap > 1) {gap = gap / 3 + 1; for (size_t I = 0; I = 0 & & a [end] > tmp) {a [end + gap] = a [end]; end-= gap } a [end + gap] = tmp;}

The time complexity and space complexity of these sorts are shown in the table below:

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.