数据结构常见排序算法 c语言实现

MoreWindows Blog 讲解的白话经典算法系类  对复习经典算法很有帮助,写得浅显易懂。

根据理解,自己写的代码如下:

 

/*************************

冒泡排序,时间复杂度o(n2)

**************************/

int* bubbleSort(int *nums ,int n){

	int temp;

	for (int i=0;i<n-1 ;i++){
		for(int j=0;j<n-i-1;j++){
			if (nums[j] > nums[j+1]){

			temp = nums[j+1];
			nums[j+1] = nums[j];
			nums[j]  = temp;


			}
		}
		
	}
	return nums;

}




/***************************************

希尔排序,第一层从n/2开始,gap逐步对折,
 第二层在元素间移动位置
 第三层用于比较相距gap个位置的元素
o(n1.5)

****************************************/

int * shellSort(int nums[], int n){
	int gap,i,j,temp;
	for (gap = n; gap > 0; gap /= 2){
		for (i = gap; i < n; i++){
			for (j=i-gap; j >= 0 && nums[j]>nums[j+gap]; j-=gap){
				temp = nums[j];
				nums[j] = nums[j+gap];
				nums[j+gap]  = temp;
				
			}
		}
	}
return nums;
}




/****************************************

直接插入排序算法
最坏时间复杂性为O(n^2),空间复杂度为O(1)。

*****************************************/

int *straightInsertionSort(int a[],int n){
	int i,j,temp;
	for(i = 1; i < n; i++){
		
		temp = a[i];
		for(j = 0; j < i ; j++)
		{
			if (temp < a[j])
				break;
			 
		}
		
			if (j <= i) {
				
				while (i != j){
					a[i] =  a[i-1];
					i--;

				}//end while

			a[j] = temp;

			}

		
	}

	return a;
}

void Insertsort2(int a[], int n)  
{  
    int i, j;  
    for (i = 1; i < n; i++)  
        if (a[i] < a[i - 1])  
        {  
            int temp = a[i];  
            for (j = i - 1; j >= 0 && a[j] > temp; j--)  
                a[j + 1] = a[j];  
            a[j + 1] = temp;  
        }  
} 


/************************************************************

直接选择排序   O(n2)

直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,
所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,
而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。

****************************************************************/

int *selectSort(int a[], int n){
	int i,j,mins;
	for (i = 0; i < n; i++){
		mins = i;
		
		for (j = i+1; j < n; j++){
			if (a[j] < a[mins]){
				mins = j;
			}
		}
		
		swap(a[mins],a[i]);

	}
return a;
}




//使用引用,如果使用异或的方法进行交换变量值,
//a,b 都引用相同的值时,会导致错误,a,b都为0 。传参数swap(i,i)


void swap(int &a, int &b){


	int c = a;  
    a = b;  
    b = c;  

//	a = a + b;
//	b = a - b;
//	a = a - b;

// 	a ^= b;  
//  b ^= a;  
//  a ^= b;  
}

/*************************************************

折半插入排序      
二分查找方法插入                    
比较时间复杂度O(nlogn)总的时间复杂度仍是 O(n2)

**************************************************/


int *binaryInsertionSort(int a[], int n){
int i,j,low,high,middle,temp;
	
	for (i = 1; i <= n-1; i++){
		low = 0;
		high = i;
		temp = a[i];

		while (low <= high) {
			middle = (low + high)/2;
			if (a[middle] < temp) {
					low = middle +1;
			}
			else  {
					high = middle -1;
				}
		}

		for (j = i;j >= high+1 ; j--){
			a[j] = a[j-1];
			
		}
		a[j] = temp;

	}


return a;
}


/********************************************************

  快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高
 该方法的基本思想是:

1.先从数列中取出一个数作为基准数。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。



对挖坑填数进行总结

1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

************************************************************/

void quickSort(int a[],int left,int right){

	if (left < right){

	int i =left;
	int j = right;
	int temp = a[left];

	while (i < j){
		while (i < j && temp <= a[j]){
			j--;	
		}
		if (i < j)
			a[i++] = a[j];
		
		while (i < j && temp > a[i]){
			i++;
		}
		if (i < j)
			a[j--] = a[i];

		
	}

	a[i] = temp;
	
	quickSort(a, left, i-1);
	quickSort(a, i+1, right);

	}
}

/***************************************************************

k&r快速排序  *qsort 函数:以递增顺序对v[left]...v[right]进行排序

*****************************************************************/


void qsort(int v[] , int left, int right){
	
	int i, last; //last 用来划分子集,表示左子集外一个
	void swap2(int v[] , int i, int j);
	
	if (left >= right)/*若数组包含的元素少于两个,则不执行任何操作*/
		return ;

	swap2(v, left, (left + right)/2 );  //将划分子集的元素,中间那个
	last = left;						//移动到v[0]
	for (i = left+1; i <= right; i++){   //划分子集
		if (v[i] < v[left]){			
			swap2(v, ++last, i);
		}
	}
	swap2(v, left, last);				//恢复划分子集的元素

	qsort(v, left, last-1);
	qsort(v, last+1, right);
}

void swap2(int v[], int i, int j){
	int temp ;
	temp = v[i];
	v[i] = v[j];
	v[j] = temp;

}


/**********************************************************************

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。
小根堆排序,输出降序排列数组

************************************************************************/


void minHeapSortDescend(int a[], int n){

	createHeap(a,n);//堆化数组
//	myPrint2(a , n  );	

	for (int i = n ; i > 0 ; i--){
		swap(a[0], a[i-1]);
		MinHeapFixDown(a, 0, i-1);
		
	}
	

}
/***************************************************************

将一个数组调整为大根堆,按算法从n/2开始循环,具体可以看下面的解释
http://blog.csdn.net/morewindows/article/details/6709644

*****************************************************************/

void  createHeap(int *a, int n) {
	for (int i = n/2 +1 ; i >= 0; i--){
		MinHeapFixDown(a, i, n);	//小根堆调整,从第一个有孩子的子节点开始调整	
	}
}

void MinHeapFixDown(int a[], int i, int n){

	for (int child = i; child < n ; ){
		int leftChild = 2 * child + 1;
		int rightChild =2 * child + 2;
		int min = 0;

		if (leftChild >= n) 
			break;

		
		if (leftChild < n && rightChild <n)
			 min = a[leftChild] > a[rightChild] ? rightChild: leftChild;//返回最小的孩子
		else
			min = leftChild;

		if (a[min] < a[child]){
			swap(a[child],a[min]);

		}
		else 
			break;
		
		child = min;
	}
}



/******************************************************************

归并排序时间复杂度o(nlogn)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法
(Divide and Conquer)的一个非常典型的应用。
数组左半边有序,右半边有序,则合并之后就全部有序,逐步递归

*********************************************************************/

void mergeSortArray(int a[], int n) {

	int *pTempArray =(int*) malloc(n* sizeof(int));//获取n个大小的int空间
	if (pTempArray == NULL)
		return ;

	int mid = n / 2;
	myMergeSort(a, 0, n-1, pTempArray);
	
	free(pTempArray);
	
}

void myMergeSort(int a[], int first , int last, int temp[]){
	if (first < last ){
		int mid = first + (last - first)/2 ;
		myMergeSort(a, first, mid, temp);
		myMergeSort(a, mid+1, last, temp);
		mergeArray(a, first, mid, last, temp );

	}

}


void mergeArray(int a[], int first, int mid, int last, int temp[]){

	int k = first;
	int i = first;
	int j = mid +1;

	for  (; i <= mid && j <= last; ){
			if(a[i] < a[j])
				temp[k++] = a[i++];
			else
				temp[k++] = a[j++];
	}

	while(i <= mid){
		temp[k++] = a[i++];
			
	}

	while (j <= last){
		temp[k++] = a[j++];
	}

	for (i=first; i<= last; i++){
		a[i] = temp[i];
	}

}





运行结果:
sort1

 

有个排序算法的动态图,看起来挺好玩的。

分享一下

 

 

Tagged on: ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据