C++ nine sort specific implementation code
- 2020-08-22 22:27:21
- OfStack
The content of this article will be updated according to the needs of bloggers, I hope you will pay more attention.
Direct insertion sort
void InsertSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 1; i < n; ++i)
{
for(int j = i - 1; j >= 0; --j)
{
if(r[j+1] < r[j])
{
int s = r[j+1];
r[j+1] = r[j];
r[j] = s;
}
}
}
}
Half insertion sort
void BinInsertSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 1; i < n; ++i)
{
int s = r[i];
int low = 0;
int high = i - 1;
while(low <= high)
{
int mid = (low + high) / 2; //mid The position is the number you're looking for
if(s < r[mid])
high = mid - 1;
else
low = mid + 1;
}
for(int j = i - 1; j >= high + 1; --j) //high+1 namely mid , the number of executions moved back until mid The number of ward
r[j+1] = r[j];
r[high+1] = s; //mid The location is itself
}
}
Hill sorting
void ShellSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
int step = n / 2;
while(step >= 1)
{
for(int i = step; i < n; ++i)
{
for(int j = i - step; j >= 0; j -= step)
{
if(r[j+step] < r[j])
{
int s = r[j+step];
r[j+step] = r[j];
r[j] = s;
}
}
}
step /= 2;
}
}
Direct selection sort
void SelectSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 0; i < n - 1; ++i)
{
int samll = i;
for(int j = i + 1; j < n; ++j)
{
if(r[small] > r[j])
samll = j;
}
if(small != i)
{
int s = r[i];
r[i] = r[small];
r[small] = s;
}
}
}
Heap sort
void HeapAdjust(int r[]; int i; int j) // Adjust the heap
{
int child = 2 * i;
int s = r[i]; //s Temporary storage of node data
while(child <= j)
{
if(child < j && r[child+1] > r[child]) // To compare 2 Is the tree
++child;
if(s >= r[child]) // Nodes compared to large subtrees
break;
r[child/2] = r[child]; // If the big subtree is bigger than the node, interchange
child = 2 * child; // Continue to retrieve to the subtree
}
r[child/2] = s; // The number of nodes is the largest number
}
void HeapSort(int r[]) // Building the heap
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = n / 2 - 1; i >= 0; --i) // only n/2-1 It's the subtree that has the index before it
{
HeapAdjust(r, i, n - 1); // Big top heap is constructed, the nodes are all larger than the subtree, and the last root node is the largest number
}
for(int i = n - 1; i > 0; --i)
{
// Interchanges the current top heap element with the current tail element, moving the largest number to the end
int s = r[0];
r[0] = r[i];
r[i] = s;
HeapAdjust(r, 0, i -1); // Adjust the remaining elements until you get from small to large
}
}
Bubble sort
void BubbleSort(int r[])
{
int n = sizeof(r) / sizeof(r[0]);
for(int i = 0; i < n - 1; ++i)
{
for(int j = 0; j < n - 1 - i; ++j)
{
if(r[j] > r[j+1])
{
int s = r[j];
r[j] = r[j+1];
r[j+1] = s;
}
}
}
}
Quick sort
int Partition(int r[], int low, int high)
{
int pivotkey = r[low];
int i = low;
int j = high;
while(i < j)
{
while(i < j && r[j] > pivotkey) // from j Go ahead and find the number one 1 than pivotkey A small number of
--j;
if(i < j)
{
r[i] = r[j];
++i;
}
while(i < j && r[i] < pivotkey) // from i Go back and find the number one 1 than pivotkey A large number of
++i;
if(i < j)
{
r[j] = r[i];
--j;
}
}
r[j] = pivotkey; // Complete the final exchange
return j; // Returns the cut-off point, the ratio of the previous Numbers pivotkey It's smaller than everything else pivokey big
}
void QuickSort(int r[], int low, int high) // The array, 0 And the length of the -1
{
if(low < high)
{
int pivot = Partition(r, low, high);
QuickSort(r, low, pivot - 1); // Recursion, the first half of this is quicksort
QuickSort(r, pivot + 1; high); // Recursion, the second half of the quicksort continues
}
}
Merge sort
void copyArray(int source[], int dest[], int len, int first)
{
int i;
int j = first;
for(i = 0; i < len; ++i)
{
dest[j] = source[i];
++j;
}
}
void merge(int a[], int left, int right)
{
int begin1 = left;
int mid = (left + right) / 2;
int begin2 = mid + 1;
int newArrayLen = right - left + 1;
int *b = (int*)malloc(newArrayLen * sizeof(int));
int k = 0;
while(begin1 <= mid && begin2 <= right) // To find out 2 The smaller number in the group is put in order b space
{
if(a[begin1] <= a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
// Put the rest in b space
while(begin1 <= mid)
b[k++] = a[begin1++];
while(begin2 <= right)
b[k++] = a[begin2++];
copyArray(b, a, newArrayLen, left); // the b The number of Spaces is written back to the original array
free(b);
}
void MergeSort(int r[], int left, int right) // The array, 0 And the length of the -1
{
int i;
// At least two elements are sorted
if(left < right)
{
i = (left + right) / 2;
MergeSort(r, left, i); // The first half is recursion
MergeSort(r, i + 1, right); // The second half is recursion
merge(r, left, right); //10 The order of comparison of Numbers is [0,1][0,2][3,4][0,4][5,6][5,7][8,9][5,9][0,9]
}
}
Bucket sort
void insert(list<int> &bucket, int val)
{
auto iter = bucket.begin();
while(iter != bucket.end() && val >= *iter)
++iter;
//insert Will be in iter I'm going to insert the data before, so that the sort is stable
bucket.insert(iter, val);
}
void BuckdeSort(vector<int> &arr)
{
int len = arr.size();
if(len <= 1)
return;
int min = arr[0], max = min;
for(int i = 1; i < len; ++i) // Find the minimum and maximum
{
if(min > arr[i])
min = arr[i];
if(max < arr[i])
max = arr[i];
}
int k = 10; // The size of the barrel
// Round up, for example [0,9] There are 10 The number, we have theta (9-0)/k+1=1 A barrel
int bucketsNum = (max - min) / k + 1; // The number of barrels
vector<list<int>> buckets(bucketsNum);
for(int i = 0; i < len; ++i)
{
int value = arr[i];
//(value-min)/k It's in that bucket
insert(buckets[(value-min)/k], value); // Put the data into buckets and sort them
}
int index = 0;
for(int i = 0; i < bucketsNum; ++i)
{
if(buckets[i].size())
{
for(auto &value : buckets[i])
arr[index++] = value;
}
}
}