Comparative analysis of C sorting Algorithm
- 2020-11-25 07:30:35
- OfStack
This paper analyzes various sorting algorithms of C#. Share to everybody for everybody reference. The specific analysis is as follows:
Firstly, the time complexity and stability of different sorting algorithms are compared by the chart.
|
排序方法 |
平均时间 |
最坏情况 |
最好情况 |
辅助空间 |
稳定性 |
| 直接插入排序 |
O(n2) |
O(n2) |
O(n) |
O(1) |
是 |
| 冒泡排序 |
O(n2) |
O(n2) |
O(n) |
O(1) |
是 |
| 简单选择排序 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
是 |
| 希尔排序 | - |
O(nlog2n)~O(n2) |
O(nlog2n)~O(n2) |
O(1) |
否 |
| 快速排序 |
O(nlog2n) |
O(n2) |
O(nlog2n) |
O(log2n) |
否 |
| 堆排序 |
O(nlog2n) |
O(nlog2n) |
O(nlog2n) |
O(1) |
否 |
| 2-路归并排序 |
O(nlog2n) |
O(nlog2n) |
O(nlog2n) |
O(n) |
是 |
| 基数排序 | O(d(n + rd)) | O(d(n + rd)) | O(d(n + rd)) | O(rd) | 是 |
1. Time complexity of the algorithm 1. In general, it refers to the asymptotic time complexity in the worst case.
2. The stability of sorting algorithm will influence the multi-keyword sorting.
The different sorting algorithms are illustrated in the C# code below
Insertion sort
Time complexity: Average case -- O(n2) Worst-case -- O(n2) Auxiliary space: O(1) Stability: Stable
Insertion sort inserts 1 element at a time on the basis of an already ordered small sequence. And, of course, to start with this little ordered sequence there's only one element, which is the first element. The comparison starts at the end of an ordered sequence, that is, the element to be inserted and the largest already ordered. If it is larger, it is inserted directly after it. Otherwise, 1 goes straight ahead until it finds its place to be inserted. If you encounter an element that is equal to the insert element, the insert element places the element that you want to insert after the element that is equal. Therefore, the order of equal elements does not change, the order out of the original unordered sequence is the sorted order, so the insertion sort is stable.
void InsertSort(SqList &L) {
// The order sheet L Do direct insertion sort.
int i,j;
for (i=2; i<=L.length; ++i)
if (LT(L.r[i].key, L.r[i-1].key)) {
// "<" When need to L.r[i] Insert ordered subtables
L.r[0] = L.r[i]; // Copy as a sentinel
for (j=i-1; LT(L.r[0].key, L.r[j].key); --j)
L.r[j+1] = L.r[j]; // Records backwards
L.r[j+1] = L.r[0]; // Insert into the correct position
}
} // InsertSortHill sort (shell)
Time complexity: Ideal-Case - O(nlog2n) Worst-case - O(n2) Stability: unstable
Hill sort is to insert the elements according to the length of asynchronization. When the elements are disordered at the beginning, the step size is the largest, so the number of elements inserted in the sort is small and the speed is very fast. When the elements are basically ordered and the step size is small, insertion sort is very efficient for ordered sequences. Therefore, the time complexity of Hill sort is 1 better than o(n^2). Due to multiple insertion sorts, we know that the first insertion sort is stable and does not change the relative order of the same elements. However, in different insertion sorts, the same elements may move in their respective insertion sorts, and their stability will be disturbed at last. Therefore, shell sort is unstable.
void ShellInsert(SqList &L, int dk) {
// The order sheet L As a 1 Wade Hill insertion sort. This algorithm matches the algorithm 10.1 The following modifications have been made:
// 1. The increment of the record position before and after is dk Rather than 1 ;
// 2. r[0] Just a CD, not a sentinel. when j<=0 , the insertion location has been found.
int i,j;
for (i=dk+1; i<=L.length; ++i)
if (LT(L.r[i].key, L.r[i-dk].key)) { // Should be L.r[i] Insert the ordered increment quantum table
L.r[0] = L.r[i]; // Temporary existence L.r[0]
for (j=i-dk; j>0 && LT(L.r[0].key, L.r[j].key); j-=dk)
L.r[j+dk] = L.r[j]; // Record back and find the insertion location
L.r[j+dk] = L.r[0]; // insert
}
} // ShellInsert
void ShellSort(SqList &L, int dlta[], int t) {
// In incremental sequence dlta[0..t-1] The order sheet L Let's put it in hill's order.
for (int k=0;k<t;k++)
ShellInsert(L, dlta[k]); // 1 Trip to increment of dlta[k] Insertion sort
} // ShellSortBubble sort
Time complexity: Average case - O(n2) Worst case - O(n2) Auxiliary space: O(1) Stability: Stable
Bubble sort is when you move the smaller elements forward or the larger elements back. A comparison is a comparison of two adjacent elements, and swapping also occurs between these two elements. So, if these two elements are equal, I don't think you're going to be bored swapping them for one; If two equal elements are not adjacent, then even if two elements are adjacent by the previous pair-swap, they will not be exchanged at this time, so the order of the same elements before and after does not change, so bubble sort is a stable sorting algorithm.
void BubbleSort(SeqList R) {
int i . j;
Boolean exchange; // Exchange of mark
for(i=1;i<n;i++){ exchange="FALSE;" j="n-1;j">=i;j--) // For the current unordered region R[i..n] Scan from bottom to top
if(R[j+1].key< R[j].key){// Exchange record
R[0]=R[j+1]; //R[0] Not a sentinel, just a CD
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE; // An exchange has occurred, so the exchange flag is set to true
}
if(!exchange) // No swap occurs in this sequence, so the algorithm is terminated in advance
return;
} //endfor( Outer loop )
}Quick sort
Time complexity: Mean case - O(nlog2n) Worst case - O(n2) Auxiliary space: O(log2n) Stability: unstable
Quicksort has two directions, i subscript 1 on the left goes straight to the right when a[i]
<
= a[center_index], where center_index is the array index of the central element, 1 is generally taken as the 0th element of the array. And j on the right goes straight to the left, when a[j]
>
a [center_index]. If i and j can't move, i
<
= j, exchange a[i] and a[j], repeat until i
>
j. Exchange a[j] and a[center_index], complete 1 trip of quick sort. In the central element and a [j] exchange, is likely to upset the stability of the front element, such as a sequence of 5 3, 3, 4, 3, 8 9 10 11 central elements now 5 and 3 (the fifth element, the subscript starting from 1 meter) exchange will upset the stability of the element 3, so quick sort is an unstable sorting algorithms, instability occurs in the central element and a [j] exchange time.
int Partition(SqList &L, int low, int high) {
// Interchange sequence table L Neutron sequence L.r[low..high] To put the pivot in place,
// And returns its location, at which point the records before (after) it are not larger (smaller) than it
KeyType pivotkey;
RedType temp;
pivotkey = L.r[low].key; // Use the subtable of the order 1 A pivot record
while (low < high) { // Scan alternately from both ends of the table to the middle
while (low < high && L.r[high].key>=pivotkey) --high;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp; // Swap records that are smaller than the pivot record to the low end
while (low < high && L.r[low].key < =pivotkey) ++low;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp; // Swap records larger than the pivot record to the high end
}
return low; // Returns the pivot position
} // Partition
void QSort(SqList &L, int low, int high) {
// The order sheet L Subsequence of L.r[low..high] Do quick sort
int pivotloc;
if (low < high) { // Length is greater than the 1
pivotloc = Partition(L, low, high); // will L.r[low..high]1 Divided into 2
QSort(L, low, pivotloc-1); // Sort the low subtables recursively, pivotloc It's the pivot position
QSort(L, pivotloc+1, high); // Sort high subtables recursively
}
} // QSort
void QuickSort(SqList &L) {
// The order sheet L Do quick sort
QSort(L, 1, L.length);
} // QuickSortSelection sort
Time complexity: Average case -- O(n2) Worst-case -- O(n2) Auxiliary space: O(1) Stability: unstable
Selection sort selects the smallest element in each position, for example, the smallest element in the first position, the second smallest element in the remaining elements, and so on, until the n-1 element, n element is not selected, because only it has the largest element left. Then, in 1 selection, if the current element is smaller than 1 element, and the smaller element appears after 1 element that is equal to the current element, the stability after the exchange is broken. For example, the sequence 5, 8, 5, 2, and 9, we know that choosing the first element 5 in the first pass will swap with the 2, so the relative order of the 2 5s in the original sequence will be broken, so the selection sort is not a stable sorting algorithm.
void SelectSort(SqList &L) {
// The order sheet L Make a simple selection sort.
int i,j;
for (i=1; i < L.length; ++i) { // Select the first i Small records and swap in place
j = SelectMinKey(L, i); // in L.r[i..L.length] Select the key Minimum record
if (i!=j) { // L.r[i] Please - L.r[j]; With the first i Record exchange
RedType temp;
temp=L.r[i];
L.r[i]=L.r[j];
L.r[j]=temp;
}
}
} // SelectSortHeap sort
Time complexity: Average case -- O(nlog2n) Worst case -- O(nlog2n) Auxiliary space: O(1) Stability: unstable
We know that the structure of the heap is node i, whose children are 2*i and 2*i+1 nodes. Large topheap requires the parent node to be greater than or equal to its two children, while small topheap requires the parent node to be less than or equal to its two children. For a sequence of length n, the process of heap sorting starts from n/2 and selects the maximum (large topheap) or the minimum (small topheap) with three values from its child nodes. The choice between these three elements will certainly not destroy the stability. But when n/2-1, n/2-2... When these parent nodes select elements, the stability is destroyed. It is possible that n/2 parent nodes swap the next element, while n/2-1 parent nodes swap the next identical element without swapping, so the stability between the two identical elements is destroyed. So heap sort is not a stable sort algorithm
void HeapAdjust(HeapType &H, int s, int m) {
// known H.r[s..m] Keyword division recorded in H.r[s].key That satisfies the definition of heap,
// Function adjustment H.r[s] The keyword, make H.r[s..m] Become a 1 A big heap
// (for the keywords recorded therein)
int j;
RedType rc;
rc = H.r[s];
for (j=2*s; j < =m; j*=2) { // Along the key Larger children are filtered down
if (j < m && H.r[j].key < H.r[j+1].key) ++j; // j for key The subscript of a larger record
if (rc.key >= H.r[j].key) break; // rc Should be inserted in position s on
H.r[s] = H.r[j]; s = j;
}
H.r[s] = rc; // insert
} // HeapAdjust
void HeapSort(HeapType &H) {
// The order sheet H Do heap sort.
int i;
RedType temp;
for (i=H.length/2; i>0; --i) // the H.r[1..H.length] Build a big top pile
HeapAdjust ( H, i, H.length );
for (i=H.length; i>1; --i) {
temp=H.r[i];
H.r[i]=H.r[1];
H.r[1]=temp; // Records the top of the heap with the current unsorted subsequence Hr[1..i] In the
// The last 1 The records are exchanged
HeapAdjust(H, 1, i-1); // will H.r[1..i-1] Readjust to large top heap
}
} // HeapSortMerge sort
Time complexity: Average case -- O(nlog2n) Worst case -- O(nlog2n) Auxiliary space: O(n) Stability: stable
Merge sort is to recursively divide the sequence into short sequences. Recursive exits are short sequences with only 1 element (considered to be directly ordered) or 2 sequences (1 comparison and exchange), and then merge each ordered segment sequence into an ordered long sequence, and continue to merge until the original sequence is all sorted. You can see that when you have one or two elements, one element is not swapped, and if the two elements are the same size and no one intentionally swapped, that doesn't undermine stability. So, in the process of merging short ordered sequences, is the stability destroyed? No, during the merge process we can guarantee that if the two current elements are equal, we will save the elements in the previous sequence in front of the resulting sequence, thus ensuring stability. So merge sort is also a stable sort algorithm.
void Merge (RedType SR[], RedType TR[], int i, int m, int n) {
// Will be ordered SR[i..m] and SR[m+1..n] Merge is ordered TR[i..n]
int j,k;
for (j=m+1, k=i; i < =m && j < =n; ++k) {
// will SR Records are incorporated from small to large TR
if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i < =m) // TR[k..n] = SR[i..m]; The remaining SR[i..m] Copied to the TR
while (k < =n && i < =m) TR[k++]=SR[i++];
if (j < =n) // The remaining SR[j..n] Copied to the TR
while (k < =n &&j < =n) TR[k++]=SR[j++];
} // Merge
void MSort(RedType SR[], RedType TR1[], int s, int t) {
// will SR[s..t] Merge sort is TR1[s..t] .
int m;
RedType TR2[20];
if (s==t) TR1[t] = SR[s];
else {
m=(s+t)/2; // will SR[s..t] Divide the for SR[s..m] and SR[m+1..t]
MSort(SR,TR2,s,m); // Will recursively SR[s..m] Merge is ordered TR2[s..m]
MSort(SR,TR2,m+1,t); // will SR[m+1..t] Merge is ordered TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // will TR2[s..m] and TR2[m+1..t] Merge into TR1[s..t]
}
} // MSort
void MergeSort(SqList &L) {
// The order sheet L Merge sort.
MSort(L.r, L.r, 1, L.length);
} // MergeSortHopefully this article has helped you with your C# programming.