排序算法.md

Posted on

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InsertSort(int* a,int len)
{
    int begin = 1;
    int i = 0;
    while(begin < len)
    {
        int key = a[begin];
        for(i = begin-1;i>=0;i--)
        {
            if(a[i]<=key)    //稳定的
            {
                a[i+1] = key;
                break;
            }
            a[i+1] = a[i];
        }
        if(i<0)
            a[0] = key;//说明找完了整个有序子序列都没找到
        begin++;
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubble_sort(int arr[],int size)
{
	int i=0,j=0;
	for(i=0;i<size;i++){
		for(j=0;j<size-i-1;j++){
			if(arr[j]>arr[j+1]){
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void swap(int *a,int *b)
{
	int tmp=*a;
	*a=*b;
	*b=tmp;
}
void adjust_down(int arr[],int root,int size)
{
	int parent=root;
	int left=root*2+1;
	int right=left+1;
	while(left<size){
		int max=left;
		if(right<size && arr[right]>arr[max]){
			max=right;
		}
		if(arr[max]>arr[parent]){
			swap(&arr[max],&arr[parent]);
			parent=max;
			left=parent*2+1;
			right=left+1;
		}
		else{
			break;
		}
	}
}
//make min heap
void heap_sort(int arr[],int size)
{
	int begin=0;
	for(begin=size/2-1;begin>=0;--begin){
		adjust_down(arr,begin,size);
	}
	int end=size-1;
	while(end>0){
		swap(&arr[0],&arr[end]);
		adjust_down(arr,0,end);
		--end;
	}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quick_sort(int arr[],int left,int right)
{
	if(left>=right){
		return;
	}
	int key=arr[left];
	int begin=left;
	int end=right;
	while(begin!=end){
		while(begin<end && arr[end]>=key){
			end--;
		}
		if(end>begin){
			arr[begin]=arr[end];
		}
		while(begin<end && arr[begin]<=key){
			begin++;
		}
		if(begin<end){
			arr[end]=arr[begin];
		}
	}
	arr[begin]=key;
	quick_sort(arr,left,begin-1);
	quick_sort(arr,begin+1,right);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void merge(int* src,int *dst,int begin,int mid,int end)
{
	int begin1=begin;
	int begin2=mid;
	int index=begin;
	while(begin1<mid && begin2<end){
		if(src[begin1]<src[begin2]){
			dst[index++]=src[begin1++];
		}else{
			dst[index++]=src[begin2++];
		}
	}
	while(begin1<mid){
		dst[index++]=src[begin1++];
	}
	while(begin2<end){
		dst[index++]=src[begin2++];
	}
	memcpy(src+begin,dst+begin,(end-begin)*sizeof(int));
}
void _merge_sort(int *arr,int* tmp,int left,int right)
{
	if(left+1>=right){
		return;
	}
	int mid=left+(right-left)/2;
	_merge_sort(arr,tmp,left,mid);
	_merge_sort(arr,tmp,mid,right);
	merge(arr,tmp,left,mid,right);
}
void merge_sort(int* arr,int size)
{
	int* tmp=(int*)malloc(size*sizeof(int));
	_merge_sort(arr,tmp,0,size);
	free(tmp);
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void select_sort(int arr[],int size)
{
	int i=0,j=0;
	int k=0;
	for(i=0;i<size;i++){
		k=i;
		for(j=i+1;j<size;j++){
			if(arr[k]<arr[j]){
				k=j;
			}

		}
		if(k!=i){
			int tmp=arr[k];
			arr[k]=arr[i];
			arr[i]=tmp;
		}
	}
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void shellSort(int *a,int n){

    int i,j,k,gap;
    for (gap = n / 2; gap > 0; gap = gap / 2) { //步长
        for (i = 0; i < gap; i++) {  //直接插入排序的次数；也就是在每个分组中需要进行几次直接插入排序；

            //开始进行插入排序，每次加gap的步长；
            for (j = i + gap; j < n; j = j + gap) {
                if (a[j] < a[j - gap]) {

                    //保存后面的值；
                    int temp = a[j];
                    for (k = j - gap; k >= 0 && a[k] > temp; k = k - gap) {
                        //先把前面的数往后移；
                        a[k + gap] = a[k];
                    }
                    a[k + gap] = temp;

                }
            }

        }
    }

}