八大排序算法

排序算法

1、冒泡排序

冒泡排序有一个形象的解释，每一轮，最大或者最小元素像泡泡一个浮出来，每一轮遍历都可以将一个元素放在正确位置。

template<typename T>
void BubbleSort(T a[], int len){
    for(int i=0; i<len; i++){
        for(int j=0; j<len-i-1; j++){
            if(a[j]>a[j+1])
            {
                swap(a[j], a[j+1]);
            }
        }
    }
}

2、选择排序

选择排序每一次选择一个最大或者最小的元素放在正确位置。

template<typename T>
void SelectSort(T arr[], int len){
    for(int i=0; i<len; i++){
        int min=i;
        for(int j=i+1; j<len; j++){
            if(arr[j]<arr[min]){
                min=j;
            }
        }
        swap(arr[i], arr[min]);
    }
}

3、插入排序

插入排序逐渐的维护一个已经排序好的序列，逐个将元素插入这个序列。

template<typename T>
void InsertSort(T arr[], int len){
    for(int i=1; i<len; i++){
        int key=arr[i];
        int j=i-1;
        while(j>=0 && key<arr[j]){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key;
    }
}

4、希尔排序

希尔排序是插入排序的改进版，也叫 “缩小增量排序”。插入排序维护的序列间隔总是1，而希尔排序是按照增量分组，逐步减少增量至1，每个分组内部实现插入排序，效率优于普通插入排序。

template<typename T>
void ShellSort(T arr[], int len){
    int gap=1;
    while(gap<len/3){
        gap=gap*3+1;
    }
    while(gap>=1){
        for(int i=gap; i<len; i++){
            for(int j=i; j>gap && arr[j]<arr[j-gap]; j-=gap){
                swap(arr[j], arr[j-gap]);
            }
        }
        gap/=3;
    }
}

5、快速排序

void qsort(vector<int>&data, size_t s, size_t e) {
    if(s>=e || s>data.size() || e>data.size()) return;
    size_t mid = (s+e)/2;int val = data[mid];
    // cout << val << endl;
    size_t start=s, end=e;
    while(s<e) {
        while(data[s] < val && s<e) {
            s++;
        }
        while(data[e] > val && s<e){
            e--;
        }
        swap(data[s], data[e]);
    }
    // cout << data[s] << endl;
    qsort(data, start, s-1);
    qsort(data, s+1, end);
}

6、堆排序

void sift_down(int arr[], int start, int end){
    int parent = start;
    int child = 2*start+1;
    while(child<=end){
        if(child+1<=end && arr[child]<arr[child+1])
            child++;
        if(arr[parent]>arr[child])
            return ;
        else{
            swap(arr[parent], arr[child]);
            //往下调整
            parent=child;
            child=2*parent+1;
        }
    }
}
void heap_sort(int arr[], int len){
    //调整为大根堆，从最后一个父元素开始(len-1-1)/2
    for(int i=(len-1-1)/2; i>=0; i--) sift_down(arr, i, len-1);
    //将堆的根（最大值）掉换到最后一个元素（从小到大排序），在重新调整为大根堆
    for(int i=len-1; i>=0; i--){
        swap(arr[0], arr[i]);
        sift_down(arr, 0, i-1);
    }
}

7、归并排序

一半一半砍开来，砍成只有两个元素之后，归并。

template<typename T>
void merge_sort1(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {//区间长度
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }

    if (a != arr) {//这里没有看懂
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }

    delete[] b;
}

8、桶排序

将数据放到到各个桶中，在插入数据的时候每个桶的数据保持有序，所以每个桶相当于是一个有序链表。最后将各个桶合并起来，即将各个链表Merge，形成一个有序的整体。

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;// 桶的个数

/**
 *链表结构体
 */
struct ListNode{
	explicit ListNode(int i=0):mData(i),mNext(NULL){}
	ListNode* mNext;
	int mData;
};

/**
 * 插入的时候是有序的，返回值是头节点
 */
ListNode* insert(ListNode* head,int val){
	ListNode dummyNode;
	ListNode *newNode = new ListNode(val);
	ListNode *pre,*curr;
	dummyNode.mNext = head;
	pre = &dummyNode;
	curr = head;
	while(NULL!=curr && curr->mData<=val){
		pre = curr;
		curr = curr->mNext;
	}
	newNode->mNext = curr;
	pre->mNext = newNode;
	return dummyNode.mNext;
}

/**
 * 将两个链表合并，合并后仍然保持有序
  */
ListNode* Merge(ListNode *head1,ListNode *head2){
	ListNode dummyNode;
	ListNode *dummy = &dummyNode;
	while(NULL!=head1 && NULL!=head2){
		if(head1->mData <= head2->mData){
			dummy->mNext = head1;
			head1 = head1->mNext;
		}else{
			dummy->mNext = head2;
			head2 = head2->mNext;
		}
		dummy = dummy->mNext;
	}
	if(NULL!=head1) dummy->mNext = head1;
	if(NULL!=head2) dummy->mNext = head2;
	
	return dummyNode.mNext;
}

/**
 * 桶排序主体部分
 */
void BucketSort(int n,int arr[]){
	vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));// 存的是每个桶的头节点，一个桶相当于是一个有序链表
	for(int i=0;i<n;++i){
		int index = arr[i]/BUCKET_NUM; // 看要将数据放在哪个桶里面
		ListNode *head = buckets.at(index);// 局部变量
		buckets.at(index) = insert(head,arr[i]);// 插入桶中
	}
	ListNode *head = buckets.at(0); // 初始值是第0个桶
	for(int i=1;i<BUCKET_NUM;++i){
		head = Merge(head,buckets.at(i)); // 将两个桶合并
	}
	for(int i=0;i<n;++i){
		arr[i] = head->mData;
		head = head->mNext;
	}
}

9、折半插入排序

template <typename T>
void insertSort1(vector<T> &v){
    int n=v.size();
    for(int i=1; i<n; i++){
        int l=0, r=i-1;
        T key=v[i];
        int mid;
        while(l<=r){
            mid=(l+r)/2;
            if(key < v[mid]) r=mid-1;
            else l=mid+1;
            //寻找第一个大于key的位置，所以直接使用else，<=的元素都不需要管
        }
        int k;
        for(k=i-1; k>r; k--) v[k+1]=v[k];
        v[k+1]=key;
    }
}