arrange in order
1. Bubble Sort
void bubblesort1(int* arr, unsigned int len)
{
// no need to sort if length is less than 2
if (len < 2) return;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1])
swap(arr[j + 1], arr[j]);
}
}
}
//Bubble sort is implemented using a recursive approach
void bubblesort2(int* arr, unsigned int len)
{
if (len < 2) return;
for (int i = 0; i < len - 1; i++) {
if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
}
bubblesort2(arr, --len);
}
2. Selection sorting
// Using a non-recursive method, the smallest value is selected each round and exchanged with the first element
void selectsort1(int* arr, int len)
{
int i = 0, j = 0, min = 0;
for (i = 0; i < len - 1; i++) {
min = i; for (int j = i + 1)
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) min = j;
}
if (min ! = i) swap(arr[i], arr[min]);
}
}
// Using a non-recursive method, the smallest and largest values are selected in each round, the largest is exchanged with the last element, and the smallest is exchanged with the first element
void selectsort2(int* arr, int len)
{
int i = 0, j = 0, min = 0, max = 0;
for (int i = 0; i < len / 2; i++) {
for (int i = 0; i < len / 2; i++) { min = i.
max = len - 1 - i; for (int j = i + 1 + 1; i++) { min = i; max = 0
for (int j = i + 1; j < len - i; j++) {
if (arr[j] < arr[min]) min = j; if (arr[j] < arr[min])
if (arr[j] > arr[max]) max = j;
}
if (i!=min) swap(arr[min], arr[i]);
if(len-1 - i!=max) swap(arr[max], arr[len - 1 - i]);
}
}
// Implementing the selectsort algorithm using recursive methods
void selectsort3(int* arr, int len)
{
if (len < 2) return; // Arrays less than 2 elements do not need to be sorted.
int ii; // Counter for the number of trips to sort.
int iminpos = 0; // The position (subscript of the array) of the smallest value selected by each loop.
for (ii = 1; ii < len; ii++)
{
// Find the element with the smaller value and write down its position.
if (arr[ii] < arr[iminpos]) iminpos = ii;
}
// If the smallest element in this loop is not the element at the start position, swap their positions.
if (iminpos ! = 0) swap(arr[0], arr[iminpos]);
selectsort2(arr + 1, --len);
}
3. Insertion Sort
//Direct Insertion Sort, for this algorithm, we can optimize, in the process of insertion sort, we are a step-by-step comparison, //But in fact, the previous data series it is ordered.
//but in fact the previous data series it is ordered, in fact, we can bisect the search method to find the location of the need to insert, so as to achieve the effect of insertion
void insertsort1(int* arr, int len)
{
int i, j; for ( i = 1; i & j)
for ( i = 1; i < len; i++) {
int temp = arr[i];
for ( j = i - 1; j >= 0; j--) {
if (arr[j] <= temp) break;
arr[j + 1] = arr[j];
}
//+1 because at the end j also subtracts itself once
arr[j + 1] = temp; }
}
}
//Based on the above thoughts，We improve on the direct insertion sort，Improved to binary insertion sort
void insertsort2(int* arr, int len)
{
int i, j, low, high, mid;
int temp;
for (i = 1; i < len; i++) {
if (arr[i] < arr[i - 1]) {
temp = arr[i];
low = 0; high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < arr[mid]) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) arr[j + 1] = arr[j];
arr[high + 1] = temp;
}
}
}
void Binary_InsertSort(int* arr, int length)
{
int i, j, low, high, mid,temp;
for (i = 1; i < length; i++) {
if (arr[i] < arr[i - 1]) {
temp = arr[i];
low = 0, high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > temp) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--) arr[j+1] = arr[j];
arr[high + 1] = temp;
}
}
}
4. Rapid sorting
//We want to implement the algorithm for quick sort，There are both recursive and non-recursive methods
//We now start with the0Started implementing my own algorithm for quick sorting.。
int partition(int* arr, int low, int high)
{
int i = low;
int pivot = arr[high];
for (int j = low; j < high; j++) {
if (arr[j] < pivot) swap(arr[j], arr[i++]);
}
swap(arr[i], arr[high]);
return i;
}
void quicksort(int* arr, int low, int high)
{
if (low < high) {
int mid = partition(arr, low, high);
quicksort(arr, low, mid - 1);
quicksort(arr, mid + 1, high);
}
}
5. Hill ranking
// Hill sorting
void shellsort(int *arr, int len)
{
int i, j, inc, key;
// initial increment：len/2，Divide by two after each trip
for (inc = len / 2; inc > 0; inc /= 2)
{
// Use insertion sort for each trip
for (i = inc; i < len; i++)
{
key = arr[i];
for (j = i; j >= inc && key < arr[j - inc]; j -= inc)
arr[j] = arr[j - inc];
arr[j] = key;
}
}
}
6. Counting Sort
// Code to implement counting sort
void countingsort(int arr[], int len)
{
if (len < 1) return;
// Find the largest element
int max = arr[0]; for (size_t i = 1; i < i++)
for (size_t i = 1; i < len; i++)
if (arr[i] > max) max = arr[i].
// Allocate an array of length max+1 to store the count and initialize it to 0
int* count = (int*)malloc(sizeof(int) * (max + 1));
if(count!=NULL) memset(count, 0, sizeof(int) * (max + 1));
// Count
for (size_t i = 0; i < len; i++)
count[arr[i]]++;
// Count the cumulative value of the count
for (size_t i = 1; i < max + 1; i++)
count[i] += count[i - 1];
// Create a temporary array to hold the results
int* output = (int*)malloc(sizeof(int) * len);
// Put the elements in the right places
for (size_t i = 0; i < len; i++)
{
output[count[arr[i]] - 1] = arr[i]; // put the element in the right place; // put the element in the right place; // put the element in the right place.
count[arr[i]]--;;
}
// Copy the result back to the original array
for (size_t i = 0; i < len; i++)
arr[i] = output[i]; }
}