Introduction
The 7 common sorting algorithms introduced before are all compared sorting, that is, there is a comparison process with if(arr[i] > arr[j]).
Next, we will introduce 3 typesNon-comparative sorting, its essence is to use array elementsMap to the own reference coordinate systemIn a sense, it isin advanceIt's better to help you. Therefore, in general, the efficiency of non-comparative sorting is more important than that of comparative sortinghigh。
Different ideas: counting sorting
Calculate the number of times each element appears, and then calculate the index position of each element in the sorted array, and finally complete the sorting.
principle
The principle of counting sorting is relatively simple
- Find the maximum value max and minimum value min in the array to be sorted
Determine the length range of the counting array to prepare for the subsequent occurrence of the statistical element. - Count the number of occurrences of each element
Create a count array count with length max - min + 1, traverse the array to be sorted, use the difference between the element value and the minimum value as the index of the count array, add 1 at the corresponding position to record the number of occurrences of each element. - Accumulate count array
Starting from the second element of the counting array, add the value of the current element to the previous element's value. In this way, the value of each position in the counting array represents the number of elements less than or equal to the corresponding element of the position, providing a basis for determining the position of the elements in the sorted array. - Put elements into sorted array
Create a result array result with the same length as the array to be sorted, traverse the array to be sorted from behind to forward, find its position in the counting array according to the difference between the element value and the minimum value, put the element into the corresponding position of the result array, and at the same time reduce the value of the corresponding position in the counting array by 1.
accomplish
void Sort(int[] nums)
{
//Maximum and minimum values
int max = , min = ;
foreach (int element in nums)
{
max= (max, element);
min = (min, element);
}
//Infer how big temp array needs to be created based on max min
int offset = -min;
var temp = new int[max - min + 1];
//Statistics the number of array elements appearing
foreach (int element in nums)
{
temp[element+offset]++;
}
//Accumulate count array
for (int i = 1; i < ; i++)
{
temp[i] += temp[i - 1];
}
var sort = new int[];
for (int i = - 1;i>= 0; i--)
{
sort[temp[nums[i] + offset] - 1] = nums[i];
temp[nums[i] + offset]--;
}
for(int i = 0; i < ; i++)
{
nums[i] = sort[i];
}
}Complexity analysis
- Time complexity
O(n+k), n is the array length, k is the range of values of the element (max-min+1) - Space complexity
O(k), this is quite hurt because it uses the characteristics of arrays. So the larger the value range, the larger the k is. If it is 0,999. Then you need to create the space of int[1000]. - Sorting stability
When putting elements into the sorted array, traverse the array to be sorted from behind to front to ensure that the relative order of equal elements remains unchanged. - Sort in place
Obviously not. It requires a temp array to assist.
Bucket sorting
The idea of bucket sorting is very simple, but the scope of application is also very wide. Its underlying logic is actually to divide and conquer it. Put the elements to be sortedCut toSeveral buckets are sorted separately and then merged.
It's a bit similar to merge sorting, and it's all about cutting large arrays. Therefore, bucket sorting is not an algorithm that limits logic, it is a thought. Therefore, it can be implemented for each bucketSelf-selected algorithm。
principle
- Determine the number and range of buckets
According to the maximum, minimum and data distribution of the array to be sorted, the number of buckets and the range of numerical values represented by each bucket are determined, and a mapping function is provided. - Assign elements to bucket
Iterate through the array to be sorted and put it into the corresponding bucket according to the value of the element. - Sort elements in each bucket
Other sorting algorithms (such as insert sort, quick sort, etc.) can be used to sort elements within each bucket.
Generally speaking, insertion sorting is selected because insertion sorting is a relatively simple stable sorting algorithm. Among several O(n^2) algorithms, it is relatively comprehensive. - Merge all elements in the bucket
In the order of the buckets, the elements in each bucket are taken out in turn and merged into an ordered array.
How to merge buckets? Although there is a merge arrayGeneral algorithm, but a binary heap is required, and the complexity is O(n*log k). Does not meet the requirements that do not exceed O(N)
accomplish
public static void Run()
{
int[] arr = new int[] { 1,30, 22, 94, 71, 47, 88, 25, -3, 73, 58, 4, 37, 1, 16, 92, 61, -86, 77, 13, 27, 74, 64, -44, 9, 34, -53, -19, -81, 29, 57, 42, 67, 12, 83, 20, 51, 49, 6, 32, 79, 50, 70, 15, 85, 23, 56, 45, 8, 35, 76, 52, 69, 11, 84, 24, 55, 48, 7, 33, 78, 54, 68, 10, 82, 21, 59, 46, 1, 31, 75, 5, 66, 14, 87, 26, 60, 43, 0, 36, 72, -3, 40, 17, 90, 28, 62, 41, 2, 39, -3, 65, 18, 91, 38, 93, -3, 96, 97, 98, 99 };
new BucketSort().Sort(arr, 2);
foreach (var item in arr)
{
(item);
}
}
public void Sort(int[] nums,int bucketCount)
{
int min=,max=;
foreach(int i in nums)
{
min=(min,i);
max=(max,i);
}
int offset = -min;
// Calculate the size of each bucket
int bucketSize = (max - min) / bucketCount + 1;
//Initialize the bucket
List<int>[] buckets = new List<int>[bucketCount];
for(int i = 0; i < bucketCount; i++)
{
buckets[i] = new List<int>(bucketSize);
}
//Assign elements
foreach(int num in nums)
{
//Use division to round down the index of the calculation bucket
var bucketIndex = (num + offset) / bucketSize;
buckets[bucketIndex].Add(num);
}
//Sort each bucket element
//The charm of dividing and conquering is that it can use multiple threads.
(0, bucketCount, i =>
{
InsertSort(buckets[i]);
});
//Merge Ordered Bucket
int idx = 0;
for (int i = 0; i < ; i++)
{
foreach (var item in buckets[i])
{
nums[idx] = item;
idx++;
}
}
}
public void InsertSort(List<int> arr)
{
for (int i = 0; i < ; i++)
{
for(int j = i; j > 0; j--)
{
if (arr[j] < arr[j - 1])
{
//swap
(arr[j], arr[j - 1]) = (arr[j - 1], arr[j]);
}
else
{
break;
}
}
}
}Complexity analysis
- Time complexity
The time complexity of bucket sorting mainly depends on the choice of the algorithm, and the complexity of different algorithms is different. Spread out O(n+k), where n is the length of the array to be sorted, k is the number of buckets, and at worst O(n^2). - Space complexity
Same as above, it is mainly used for storage buckets and elements in buckets. An additional n space is required to store all elements and k buckets of space. - Sorting stability
Same as above, it also depends on the choice of the algorithm. - Sort in place
Looking at the code, it is obvious that it is not.
Count expansion: cardinality sorting
The principle is to cut integers into different numbers by digits, and then compare them separately by each digit. It gradually determines the order of elements through multiple rounds of sorting, from the lowest to the highest bit.
principle
Same count sort
1. An unnecessary array
468
004
766
222
2. Sort by number first
222
004
766
468
3. Sort by ten digits
004
222
766
468
4. Sort by hundreds digits
004
222
766
468accomplish
public static void Run()
{
var arr = new int[] { 468, 004, 766, 222 };
new RadixSort().Sort(arr);
foreach (var item in arr)
{
(item);
}
}
public void Sort(int[] arr)
{
int max = ;
foreach (int i in arr)
{
max = (max, i);
}
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSortByDigit(arr, exp);
}
}
private static void CountingSortByDigit(int[] arr,int exp)
{
int n = ;
//The number is 0-9, so the bucket is fixed
int[] buckets = new int[10];
//Statistics the number of array elements appearing
for (int i = 0; i < n; i++)
{
int index = arr[i] / exp;
buckets[index % 10]++;
}
//Accumulate count array
for (int i = 1;i < 10; i++)
{
buckets[i] += buckets[i - 1];
}
int[] sort = new int[n];
for (int i = - 1; i >= 0; i--)
{
int index = arr[i] / exp;
sort[buckets[index % 10] - 1] = arr[i];
buckets[index % 10]--;
}
// Copy the output array back to the original array
for (int i = 0; i < n; i++)
{
arr[i] = sort[i];
}
}Complexity analysis
- Time complexity
O(mn), m is the number of bits of the largest element, n is the length of the array to be sorted - Space complexity
O(k), sorting of counts - Sorting stability
Stable, same count sort - Sort in place
No, sorting in the same count
Summarize
| Sorting algorithm | Average time complexity | The best time complexity | Worst time complexity | Space complexity | stability | sort by | Applicable scenarios |
|---|---|---|---|---|---|---|---|
| Select Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Unstable | Comparative sort | Small data volume and no stability requirements |
| Bubble sort | O(n^2) | O(n) | O(n^2) | O(1) | Stablize | Comparative sort | Small and basically orderly data volume |
| Insert sort | O(n^2) | O(n) | O(n^2) | O(1) | Stablize | Comparative sort | Small and basically orderly data volume |
| Hill sort | O(n^{1.3}) | O(n) | O(n^2) | O(1) | Unstable | Comparative sort | Medium-scale data sorting |
| Quick sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | Unstable | Comparative sort | The situation of large amount of data and even distribution |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stablize | Comparative sort | Large data volume and stability requirements |
| Heap sorting | O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable | Comparative sort | Large data volume, high space requirements, no stability requirements |
| Count sorting | O(n + k) | O(n + k) | O(n + k) | O(k) | Stablize | Non-comparative sorting | The case where the data range is small and is an integer |
| Bucket sorting | O(n + k) | O(n + k) | O(n^2) | O(n + k) | Stablize | Non-comparative sorting | Even distribution of data |
| Cardinality sorting | O(mn) | O(mn) | O(mn) | O(n) | Stablize | Non-comparative sorting | Integer sorting with few data bits and small range |