#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
//Sorting some sorting algorithms
//Insert sorting algorithm
//Insert directly to sort
void
direct_insert_sort(int *a,int len)
{
//Thoughts: Compare the last one with the previous one in turn
//Move the conditions that are met backwards, of course, from scratch
//Start and gradually expand from the smallest comparison array
//To the entire array
int i,j,temp;
for(i = 1;i < len;++i) {
//Get the last index data
temp = a[i];
for(j = i - 1;j >= 0;--j) {
//Start from the second to last
if(a[j] > temp)//Arrange in ascending order
a[j + 1] = a[j];
else
break;//Exit immediately
}
//Insert the last position into the appropriate position
a[j + 1] = temp;
}
}
//Hill sort
void
shell_insert_sort(int *a,int len)
{
//Thought: It's more layers than inserting the order directly
//Loop, this layer of loop is used to control stepping
//According to the original idea of the algorithm, this can reduce it
//Number of exchanges
int i,j,h,temp;
for(h = len / 2;h > 0;h /= 2) {
//In fact, the inner layer is actually inserted directly
//Algorithm ideas
//Note that i += h and i++ are calculated
//The influence of law
for(i = h;i < len;i += h) {
//Get the value of the last index
temp = a[i];
for(j = i - h;j >= 0;j -= h) {
if(a[j] > temp)//Arrange in ascending order
a[j + h] = a[j];
else
break;
}
//Insert the found position into the last index
a[j + h] = temp;
}
}
}
//Select sort
//Bubbling sort
void
bubble_swap_sort(int *a,int len)
{
//Thoughts: start with the last array
//Slowly exchange data that meets the requirements of the underlying layer
//To the upper layer, it may lead to too many exchanges
int i,j,temp;
//If there is no exchange in a bubble
//Because I think this arrangement has ended
bool exchange = false;
for(i = 0;i < len - 1;++i) {
for(j = len - 1;j > i;--j) {
//If the conditions are met, exchange it
if(a[j] < a[j - 1]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
exchange = true;
}
}
if(exchange)
exchange = false;
else
break;
}
}
//Quick sort
void
quick_swap_sort(int *a,int low,int high)
{
//Thoughts: Find a value from the array
//Then arrange the array so that both sides of it need
//It is greater than or less than this value,
//Then recursively sort
//The advantage is that you can find the intermediate value every time
//In exchange many times.
int _low,_high,qivot;
if(low < high) {
_low = low;
_high = high;
//This starts from the last one
qivot = a[low];
//The way to find the intermediate value is to gradually approach
//From the beginning and ends, and by the way
//Sorted
while(_low < _high) {
//Since it starts from low, then first
//Let's find a smaller than qivot from high (liter
//Sortate)
while(_low < _high && a[_high] > qivot)
--_high;//Gradually approaching to the middle
if(_low < _high)//The situation of a[_high] > qivot must be found
a[_low++] = a[_high];
//Now a[_high] is empty, so look for it from low
// Bigger data than qivot
while(_low < _high && a[_low] < qivot)
--_low;// Approach the middle
if(_low < _high)
a[_high--] = a[_low];
}
//Finally _low == _high Then this position is the location of qivot
a[_low] = qivot;
//Recurse
quick_swap_sort(a,low,_high - 1);
quick_swap_sort(a,_low + 1,high);
}
}
//Select sort
//Select sort directly
void
direct_select_sort(int *a,int len)
{
//Thought: It is to traverse the array and find the extreme value
//Put it to the beginning or end, gradually shrinking
//Scope to minimum comparison array
int i,j,pos,temp;
for(i = 0;i < len - 1;++i) {
//Fetch a value from scratch assuming it is an extreme value
pos = i;
for(j = i + 1;j < len;++j) {
//Satisfies
if(a[pos] > a[j])//Ascending order
pos = j;
}
if(pos != i) {
//Change the exchange
temp = a[pos];
a[pos] = a[i];
a[i] = temp;
}
}
}
void
disp(int *a,int len)
{
int i = 0;
for(;i < len;i++) {
if(i != 0 && i % 16 == 0)
printf("\n");
printf(" %d",a[i]);
}
printf("\n");
}
#define TEST_ARRAY_LEN 100000
#define TEST_COUNT 1
int
main(int argc,char *argv[])
{
//int a[] = {1,8,4,0,9,6,3,7,2,18,74,5,64,12,39};
//int len = sizeof(a) / sizeof(a[0]);
//direct_insert_sort(a,len);
//shell_insert_sort(a,len);
//bubble_swap_sort(a,len);
//quick_swap_sort(a,0,len - 1);
//direct_select_sort(a,len);
disp(a,len);
return 0;
}