　　　　Sort

=Blog= =Links= =Author=

1.各种排序算法

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法多路归并排序并分析具体情况的时间复杂度

2. 算法，排序的理解

插入（希尔排序）、选择（堆排序、归并排序）、交换（冒泡排序、快速排序）

3.插入排序

void InsertionSort( ElementType A[], int N) {
      int j, P;
      ElementType Tmp;
      for(P=1; P<N; P++) {
            Tmp = A[P];
            for(j=P; j>0 && A[j-1]>Tmp; j--)
                  A[j] = A[j-1];
            A[j] = Tmp;
      }
}

4. 堆排序

void PercDown(int a[], int i, int n){
    int tmp=0;
    int child=0;
    for(tmp=a[i]; child=2*i+1, child < n; i=child)     {
        if(child != n-1 && a[child+1]>a[child]) //看看有没有右节点，然后和右节点比较
            child++;
        if(tmp < a[child])    // 跟孩子比较，小于孩子则交换
            a[i] = a[child];
        else
            break;
    }
    a[i]=tmp;
}
void heapsort(int a[], int n){
    int i, tmp=0;
    for(i=n/2; i>=0; i--){
        PercDown(a, i, n);
    }
    for(i=n-1; i>0; i--){
        tmp = a[0];        a[0] = a[i];        a[i] = tmp;
        PercDown(a, 0, i);
    }
}

5. 冒泡排序

void BubbleSort(int arr[], int n)
{
	int i, j, k=0, tmp;
	for(i=n-1; i>=0; i--){
		k = i;
		for(j=i-1; j>=0; j--){
			if(arr[j]>arr[k])
				k = j;
		}
		if(k!=i){
			tmp = arr[i];	arr[i] =arr[k];    arr[k] = tmp;
		}
	}
}

6. 链表反转

1.1 递归反转

List RRlist(List head){
    if(head->next==NULL)   return head;
    
    List newHead = RRlist(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

1.2 普通链表反转

List ReverseList(List head){
	List p, q; 
	p=head; q=p->next;
 	while(q!=NULL){
  		p->next = q->next;
		q->next = head;
		head = q;
		q = p->next;
 	}
}

7. 交换元素a、b

swap(int *pt1,int *pt2){
	int temp;
	temp=*pt1;  *pt1=*pt2;  *pt2=temp;
}

The site is producted by @Haibin If you have some advices, you can send mail to me.