C语言插入排序

第一版

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 10
void quick_sort(int arr[], int start, int end);
int partition(int arr[], int low, int high);
void select_sort(int arr[],int n);
void insert_sort(int arr[], int n);
int main() {
	int i = 0;
	int arr[N] = {33,9,5,2,5,66,2,1,7,85};
	for (int i = 0; i < 10; i++)
	{
		printf("%d\t", arr[i]);
	}
	printf("\n");
	int n = sizeof(arr) / sizeof(arr[0]);

	insert_sort(arr,n);
	for (int i = 0; i < 10; i++)
	{
		printf("%d\t", arr[i]);
	}
	printf("\n");
	return 0;
}
//插入排序
/*
这里的算法思想是先对前两个元素排序，然后从第三个元素开始，与前一个元素比较，如果大于前一个元素，则默认有序，如果
小与前一个元素，则一直项前比较，直到找到大于自己的元素，然后将大于自己元素之后的元素一次后移即可。
*/
void insert_sort(int arr[],int n) {
	if (arr[1]<arr[0]) {//这里首先排序的原因是发现前两个元素不适用于下面的通式
		int temp = arr[1];
		arr[1] = arr[0];
		arr[0] = temp;
	}

	for (int i = 2; i < n; i++) {
		int index = i;
		
		for (int j = i-1; j >=-1; j--) {
			if((arr[j]<=arr[i] && arr[i]<arr[i-1]) || (j==-1 && arr[j+1] > arr[i])) {//这里的第一个条件是通用的，第二个条件是当前元素小于他前面的所有元素的考虑
				int temp = arr[i];
				while (index>j+1) {
					arr[index] = arr[index-1];
					index--;
				}
				arr[j+1] = temp;
				break;
			}
		}
	}
}

改进版

//插入排序
/*
这里是从前往后找合适的元素，和第一种从后往前匹配相反，因为是按升序排列，在某些情况下，第一种更快速高效
*/
void insert_sort1(int arr[], int n) {
	for (int i = 1; i < n;i++) {
		int j = 0;
		while (arr[j]<arr[i] && j<i) {
			j++;
		}
		if (i!=j) {
			int temp = arr[i];
			for (int k = i; k > j;k--) {
				arr[k] = arr[k - 1];
			}
			arr[j] = temp;
		}
	}
}