排序算法

1. 选择排序

选择排序的思想： 每次循环中从待排序的序列中选取一个最小值（按照升序排序），将这个最小值放到合适的位置

/// 选择排序
/// \param arr， 待排序的数组
/// \param n， 数组元素的个数
void selectionSort(int arr[], int n){
    for (int i = 0; i < n; ++i) {
        int curMinIndex = i;
        for (int j = i+1; j < n; ++j) {
            if(arr[curMinIndex] > arr[j]){
                curMinIndex = j;
            }
        }
        std::swap(arr[i], arr[curMinIndex]);
    }
}

2. 冒泡排序

冒泡排序中每一次循环把最大的那个元素沉淀到序列的最后面。保持前面的元素不变。

void bubbleSort(int arr[], int n)
{
	for(int i=0;i<n;++i)
	{
		for(int j=0; j<n-1-i; j++)
		{
			if(arr[j] > arr[j+1])
				swap(arr[j], arr[j+1]);
		}
	}
}

/// 冒泡排序
/// \param arr
/// \param n
void bubbleSort(int arr[], int n){
    bool isSwap = false;
    do{
        isSwap = false;
        for (int i = 1; i < n; ++i) {
            if(arr[i-1] > arr[i]) {
                swap(arr[i-1], arr[i]);
                isSwap = true;
            }
        }
    }while (isSwap);
}

3. 插入排序

插入排序在生活中见到的最典型的就是扑克牌了， 一般我们在抓牌的过程中都会按照顺序把牌按照顺序放好。再下一次抓到一张牌之后就将它插入到合适的位置。

有了上面的基础就可以编写插入排序的代码： 总体想法：给定一个数组，从第一个元素开始将它放到合适的位置。 对于第一个元素，因为当前只有一个元素，所以不用去考虑它插入的位置。那么就可以从第二个位置开始考察。第二个元素和它前面的元素对比如果比前面的元素小，那就应该交换它和它前面那个元素的位置，否则就不用管。然后考察第三个元素，和前一步一样也是考察当前元素和它前一个元素，如果比较小泽进行交换，直到它前面的元素都比它小。

template<typename T>
static void insertionSort(T *arr, int n) {
    for (int i = 1; i < n; ++i) {
        // 使用当前元素和它前面的元素比较，然后交换位置
        for (int j = i; j-1 >= 0; --j)
        {
            if(arr[j] < arr[j-1])
                swap(arr[j], arr[j-1]);
        }
    }
}

在上面的代码中存在有大量的交换操作，我们可以考虑我们先不把当前元素放好，先找到它合适的位置，然后一次放入就行了，避免不停的元素交换带来的性能损失

template<typename T>
static void insertionSort(T *arr, int n) {
    for (int i = 1; i < n; ++i) {
        // 优化！为了避免重复交换带来的效率损失，先不进行交换，
        // 而是先将元素保存着，找到合适的位置再填入
        int j;
        T val = arr[i];//当前待排序的元素
        for (j = i; j - 1 >= 0; --j) {
            if (val < arr[j - 1])
                arr[j] = arr[j - 1];
            else
                break;//找到了合适的位置，直接跳出
        }
        arr[j] = val;//经过上面的循环，j的位置就是当前元素合适插入的位置
    }
}

4. 归并排序

template <typename T>
void __merge(T arr[], int l, int mid, int r) {
    T* aux = new T[r-l+1];
    int i = l, j = mid+1, k = 0;
    while (i <= mid || j <= r){
        if(i > mid)
            aux[k++] = arr[j++];
        else if(j > r)
            aux[k++] = arr[i++];
        else if(arr[i] < arr[j])
            aux[k++] = arr[i++];
        else
            aux[k++] = arr[j++];
    }
    for (int i = l; i <= r; ++i)
        arr[i] = aux[i-l];
    delete [] aux;
}

template <typename T>
void __mergeSort(T arr[], int l, int r){
    if(l >= r)
        return;
    int mid = (l+r)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    __merge(arr, l, mid, r);
}

/// 归并排序
/// \tparam T
/// \param arr
/// \param n
template <typename T>
void mergeSort(T arr[], int n){
    __mergeSort(arr, 0, n-1);
}

5. 快速排序

template <typename T>
int __partition(T arr[], int l, int r){
    T v = arr[l];
    int j = l;
    //明确变量的定义，后续的代码都要去维护这个定义
    // arr[l+1... j] < v  &&  arr[j+1...i) > v
    for (int i = l+1; i <= r ; ++i) {
        if(arr[i] < v){
            j++;
            swap(arr[j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

template <typename T>
void __quickSort(T arr[], int l, int r){
    if(l >= r)
        return;
    int mid = __partition(arr, l, r);
    __quickSort(arr, l, mid-1);
    __quickSort(arr, mid+1, r);
}

template <typename T>
void quickSort(T arr[], int n){
    __quickSort(arr, 0, n-1);
}

6. 堆排序

/// 从索引k位置开始调整以k为根节点的二叉树为一个大根堆
/// \tparam T 数组类型
/// \param arr 待调整原数组
/// \param n   数组总元素个数
/// \param k   调整的索引位置
template <typename T>
void shiftDown(T arr, int n, int k){
    while (2*k + 1 < n){
        int j = 2 * k + 1;
        if(j + 1 < n && arr[j + 1] > arr[j])
            j = j + 1;
        if (arr[k] > arr[j])
            break;
        swap(arr[k], arr[j]);
        k = j;
    }
}

template <typename T>
void heapSort(T arr[], int n){
    for (int k = (n-1)/2; k >= 0; --k)
        shiftDown(arr, n, k);
    for (int i = n-1; i >= 0; --i) {
        swap(arr[0], arr[i]);
        shiftDown(arr, i, 0);
    }
}

基于划分的思想来找数组中第K大的数字（O(lgN)）。

int partition(int arr[], int l, int r){
    int v = arr[l];
    int j = l;
    for (int i = l+1; i <= r; ++i) {
        if(arr[i] < v){
            j++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

int nthNums(int arr[], int n, int k){
    int res = -1, l=0, r = n-1;
    while((res+1) != k){
        res = partition(arr, l, r);// [l, res-1], [res+1, r]
        if(res < k)
            l = res+1;
        else if(res > k)
            r = res-1;
    }
    return arr[res];
}

排序链表

template<typename T>
struct ListNode{
    T val;
    ListNode* pNext;
    ListNode(T &v) : pNext(nullptr) , val(v){
    }
};

class sortedList{
private:
    ListNode<int>* pHead;
public:
    sortedList(): pHead(NULL){
    }
    void addElement(int v){
        ListNode<int> *pNewNode = new ListNode<int>(v);
        // insert in the head of list.
        if(pHead == NULL || (pHead != NULL && pHead->val > v)){
            pNewNode->pNext = pHead;
            pHead = pNewNode;
        }else {
            ListNode<int>* pCur = pHead;
            while (pCur->pNext != NULL && pCur->val < v)
                pCur = pCur->pNext;

            pNewNode->pNext = pCur->pNext;
            pCur->pNext = pNewNode;
        }
    }
    void printList(){
        ListNode<int>* pCur = pHead;
        while (pCur){
            cout << pCur->val << " ";
            pCur = pCur->pNext;
        }
    }
};