Bubble sort, select sort, direct insert sort

1. Bubble sort

Existing array a[10], Every time we loop from the element a[9] Start , take a[j] And a[j-1] The comparison , If a[j] Small , Will a[j] Move forward , Continue to compare with the previous values in pairs , Will move the minimum value to the front of the array .
Outer loop n-1 Time （n Is array length ）, Each inner loop starts at the tail , use a[j] And a[j-1] Compare two by two , Small value keeps moving forward .
Time complexity O(n**2)
Code ：

#include <stdio.h>

void BubbleSort(int k[], int n)
{
    
	int i, j, temp, count1=0, count2=0;
	
	for( i=0; i < n-1; i++ )
	{
    
		for( j=n-1; j > i; j-- )
		{
    
			count1++;
			if( k[j-1] > k[j] )
			{
    
				count2++;
				temp = k[j-1];
				k[j-1] = k[j];
				k[j] = temp;
			}
		}
	}

	printf(" All in all %d Compare it to , the %d Secondary mobility ！", count1, count2);
}

int main()
{
    
	int i;
    int  a[10] = {
    5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	BubbleSort(a, 10);

	printf(" The result of sorting is ：");
	for( i=0; i < 10; i++ )
	{
    
		printf("%d", a[i]);
	}
	printf("\n\n");

	return 0;
}

2. Selection sort

Outer loop n-1 Time , Every time a[i] As a minimum , During internal circulation, it will start from... Every time [i:n-1] Minimum value found in the element of , Record the minimum subscript first , After an inner loop is executed , Then add the minimum value and a[i] Swap places .
Time complexity ：O(n**2), But it will move less than bubbling
Code ：

#include <stdio.h>

void SelectSort(int k[], int n)
{
    
	int i, j, min, temp, count1=0, count2=0;

	for( i=0; i < n-1; i++ )
	{
    
		min = i;
		
		for( j=i+1; j < n; j++ )
		{
    
			count1++;
			if( k[j] < k[min] )
			{
    
				min = j;
			}
		}

		if( min != i )
		{
    
			count2++;
			temp = k[min];
			k[min] = k[i];
			k[i] = temp;
		}
	}

	printf(" All in all %d Compare it to , the %d Secondary mobility ！", count1, count2);
}

int main()
{
    
	int i, a[10] = {
    5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	SelectSort(a, 10);

	printf(" The result of sorting is ：");
	for( i=0; i < 10; i++ )
	{
    
		printf("%d", a[i]);
	}
	printf("\n\n");

	return 0;
}

3. Direct insert sort

Divide the array into ordered and unordered areas , The initial phase assumes that the first element is already ordered , Insert the first element in the unordered area into the ordered area according to the size each time .
Time complexity ：O(n**2)

#include <stdio.h>

void InsertSort(int k[], int n)
{
    
	int i, j, temp;

	for( i=1; i < n; i++ )
	{
    
		if( k[i] < k[i-1] )
		{
    
			temp = k[i];

			for( j=i-1; k[j] > temp && j> = 0; j-- )
			{
    
				k[j+1] = k[j];
			}

			k[j+1] = temp;
		}
	}
}

int main()
{
    
	int i, a[10] = {
    5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	InsertSort(a, 10);

	printf(" The result of sorting is ：");
	for( i=0; i < 10; i++ )
	{
    
		printf("%d", a[i]);
	}
	printf("\n\n");

	return 0;
}