插入排序的三种算法C/C++
程序员文章站
2022-07-02 15:51:56
插入排序的三种算法c/c++:一、直接插入排序:1、平均时间复杂度为o(n^2)2、最好情况为o(n)3、最坏情况下为o(n^2)4、空间复杂度为o(1)。
算法实现为:
/*
*直接插入排...
插入排序的三种算法c/c++:一、直接插入排序:1、平均时间复杂度为o(n^2)2、最好情况为o(n)3、最坏情况下为o(n^2)4、空间复杂度为o(1)。
算法实现为:
/* *直接插入排序 */ #include #define maxsize 100 /* *a为待排序的数组,length为数组长度 */ void insort(int a[] , int length) ; /* *进行数组元素的输出 */ void displayarray(int a[] , int length) ; void main() { int a[maxsize] , length , i ; printf("please input the length of the array : \n") ; scanf("%d" , &length) ; //进行数组元素的接收 for(i = 0 ; i < length ; i++) { scanf("%d" , &a[i]) ; } printf("before sort... \n") ; displayarray(a , length) ; insort(a , length) ; printf("after sort... \n") ; displayarray(a , length) ; } void insort(int a[] , int length) { //临时储存元素 int temp ; int i , j ; for(i = 1 ; i < length ; i++) { temp = a[i] ; j = i - 1 ; while(temp < a[j] && j >= 0) { a[j + 1] = a[j] ; j-- ; } a[j + 1] = temp ; } } void displayarray(int a[] , int length) { int i ; for(i = 0 ; i < length ; i++) { printf("%4d ", a[i]); } printf("\n") ; }
二、折半插入排序
1、平均时间复杂度为o(n^2)
2、最好情况为o(nlogn)
3、最坏情况下为o(n^2)
4、空间复杂度为o(1)
算法实现为:
/* *折半插入排序 */ #include #define maxsize 100 /* *a为待排序的数组,length为数组长度 */ void binsort(int a[] , int length) ; /* *进行数组元素的输出 */ void displayarray(int a[] , int length) ; void main() { int a[maxsize] , length , i ; printf("please input the length of the array : \n") ; scanf("%d" , &length) ; //进行数组元素的接收 for(i = 0 ; i < length ; i++) { scanf("%d" , &a[i]) ; } printf("before sort... \n") ; displayarray(a , length) ; binsort(a , length) ; printf("after sort... \n") ; displayarray(a , length) ; } void binsort(int a[] , int length) { int i , j , mid , low , high , temp ; for(i = 1 ; i < length ; i ++) { low = 0 ; high = i - 1 ; temp = a[i]; while(low <= high) { mid = (low + high) / 2 ; if(temp < a[mid]) { high = mid - 1 ; }else{ low = mid + 1 ; } } for(j = i - 1 ; j >= low ; j--) { a[j + 1] = a[j] ; } a[low] = temp ; } } void displayarray(int a[] , int length) { int i ; for(i = 0 ; i < length ; i++) { printf("%4d ", a[i]); } printf("\n") ; }
三、希尔排序
1、平均时间复杂度为o(n^1.5)
4、空间复杂度为o(1)
算法实现为:
/* *希尔排序 */ #include #define maxsize 100 /* *进行希尔排序 *a为待排序数组,lengh为数组长度,delta为增量数组,length1为增量数组的长度 */ void shellsort(int a[] , int lengh , int delta[] , int length1) ; /* *进行一趟希尔排序 */ void shellinsert(int a[] , int length , int delta) ; /* *进行数组的输出 */ void displayarray(int a[] , int length) ; void main() { int a[maxsize] , length , i ; int delta[maxsize] , length1 ; printf("please input the length of the array : ") ; scanf("%d" , &length) ; //进行数组元素的接收 for(i = 0 ; i < length ; i++) { scanf("%d" , &a[i]) ; } //进行增量数组的接收 printf("please input the delta's length : ") ; scanf("%d" , &length1) ; //进行数组元素的接收 for(i = 0 ; i < length1 ; i++) { scanf("%d" , &delta[i]) ; } printf("before sort... \n") ; displayarray(a , length) ; shellsort(a , length , delta , length1) ; printf("after sort... \n") ; displayarray(a , length) ; } void shellsort(int a[] , int length , int delta[] , int length1) { int i ; for(i = length1 - 1 ; i >= 0 ; i--) { shellinsert(a , length , delta[i]) ; } } void shellinsert(int a[] , int length , int delta) { int i , j , temp ; for(i = delta ; i < length ; i++) { temp = a[i] ; j = i - delta ; while(temp < a[j] && j >= 0) { a[j + delta] = a[j] ; j -= delta ; } a[j + delta] = temp ; } } void displayarray(int a[] , int length) { int i ; for(i = 0 ; i < length ; i++) { printf("%4d ", a[i]); } printf("\n") ; }