数据结构C语言版清华大学严蔚敏（学习笔记总结6）——排序全代码：冒泡排序、直接插入排序、折半排序、希尔插入排序、选择排序、堆排序、归并排序、快速排序、基数排序（另附理解笔记）

排序算法比较表格

排序算法    平均时间复杂度    最坏时间复杂度    空间复杂度     是否稳定
冒泡排序     O（n2）                 O（n2）                O（1）          是
选择排序     O（n2）                 O（n2）               O（1）         不是
直接插入排序 O（n2）              O（n2）               O（1）           是
归并排序 O(nlogn)                     O  (nlogn)             O（n）            是
快速排序 O(nlogn)                     O（n2）                O（logn）      不是
堆排序 O(nlogn)                         O(nlogn)                O（1）          不是
希尔排序 O(nlogn)                      O（ns）                 O（1）         不是
计数排序 O(n+k)                        O(n+k)                    O(n+k)            是
基数排序 O(N∗M)                        O(N∗M)                 O(M)                是
 

//冒泡
void bubble_sort(int arr[],size_t n){
	size_t i,j;
	for(i=1;iarr[j]){
				swap(&arr[j-1],&arr[j]);		
				hasSwap = true;
			}
		}
		if(!hasSwap){
			break;	
		}
	}
}

void insert_sort(int arr[],size_t n){
     int i,j;
     for(i=1;i=0 && arr[j]>key;j--){
             arr[j+1] = arr[j];
         }
         arr[j+1] = key;
     }
}

void bin_insert_sort(int arr[],size_t n){
	int i,j;
	for(i=1;i 
 4.希尔插入排序 
//希尔排序
void shell_sort(int arr[],size_t n){
	size_t step;
	//分组
	for(step = n/2;step > 0; step = step/2){//step步长
		size_t i;
		//除了每组第一个元素以外 组内每个元素相隔step
		//对于后面所有的元素都要进行组内插入排序
		for(i=step;i=0 && arr[j]>key;j=j-step){//和组内元素比较
				arr[j+step] = arr[j];	
			}
			arr[j+step] = key;
		}
	}
}
 
 5.选择排序 
void choice_sort(int arr[],size_t n){
     size_t i,j;
     for(i=0;iarr[m]){
                  m = j;
              }
          }
          if(n-i-1 != m){
              swap(&arr[n-1-i],&arr[m]);
          }
     }
}
 
 6.堆排序 
 
 
void reheap(int arr[],size_t index,size_t n){
	size_t child = 2*index+1;
	int key = arr[index];
	while(child < n){
		if(child+1 < n && arr[child]< arr[child+1]){
			++child;
		}
		if(key
 
 
 
void max_heapify(int arr[], int start, int end) 
{
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)  //若子节点指标在范围内才做比较
        {
            if (son + 1 <= end && arr[son] < arr[son + 1]) 
            //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
            return;
        else  //否则交换父子内容再继续子节点和孙节点比较
        {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
 
void heap_sort1(int arr[], int len) 
{
    int i;
    //初始化，i从最後一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) 
    {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
 
7. 归并排序 
oid mergeArr(int arr[],size_t n){
	if(n<=1){
		return ;
	}
	int mid = n/2;
	int len =mid;
	int *prr = malloc(sizeof(int)*len);
	size_t i;
	for(i=0;i 
 8.快速排序 
 
 
void quick(int arr[],int left,int right){
	if(left >= right)
		return;
	int i=left,j=right;
	int key = arr[i];
	while(i=key){
			--j;	
		}	
		arr[i] = arr[j];
		while(i1)
		quick(arr,left,i-1);
	if(right-(i+1)+1>1)
 
void quick_sort(int arr[],size_t n){
	if(n<=1){
		return;
	}
	size_t i=0,j=n-1;
	int key =arr[i];
	while(i=key){
			--j;
		}
		arr[i] = arr[j];
		while(i1)
		quick_sort(arr,i);
	if(n-i-1>1)
		quick_sort(arr+i+1,n-i-1);
}
 
 9.基数排序 
void base_sort(int arr[],size_t n){
	Bucket bucket[10] = {};
	int max = arr[0];
	size_t i;
	for(i=0;i