排序算法

快速排序

对于快速排序需要了解

• 快速排序的平均复杂度？最坏复杂度？
• 是否是稳定排序？

快速排序也是一种分治算法

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include "header.h"
using namespace std;

int arrs[] = {9,1,2,3,4,6,7,4,8,4,6,3,4 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);

void Swap(int *arrs,int i,int j){
    int temp = arrs[i];
    arrs[i] = arrs[j];
    arrs[j] = temp;
}
int Partition(int arrs[],int low,int high)
{
    int key = arrs[high];
    int i=low-1,j=low;//i后面的数都比key小
    for(;j<high;j++){
       if(arrs[j]<key){
          i++;
          Swap(arrs,i,j);
       }
    }
    Swap(arrs,i+1,high);
    return i+1;
}

void quickSort(int arrs[],int low,int high)
{
    if(low < high)
    {
        int d=Partition(arrs,low,high);
        quickSort(arrs , low, d-1);
        quickSort(arrs , d+1, high);
    }
}



int main()
{
    quickSort(arrs,0,arrLen-1);
    for (int i = 0; i < arrLen; i++)
        cout << arrs[i] << endl;
    return 0;
}

归并排序

对于归并排序你需要了解

• 归并排序的空间复杂度？
• 归并的时间复杂度？
• 归并排序的实现？
• 归并排序是否是稳定排序？

归并排序运用了分治的思想，实现上采用递归的方法。

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include "header.h"
using namespace std;

int arrs[] = {9,1,2,3,4,6,7,4,8,4,6,3,4 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

bool MergeSort(int a[], int n)
{
    int *p = new int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}

int main()
{
    MergeSort(arrs, arrLen );
    for (int i = 0; i < arrLen; i++)
        cout << arrs[i] << endl;
    return 0;
}

堆排序&最大堆

对于堆排序你需要了解

• 什么是最大堆、最小堆？
• 堆排序是稳定排序么？为什么？
• 堆排序的时间复杂度是多少？
• 堆排序的过程、堆排序如何实现？

 最大堆最常用的操作就是插入、删除、排序。只要了解这几个方面就可以对堆很好的掌握。其中调整堆的实质就是下沉操作。堆排序的过程就是建立最大堆，调整堆的过程。插入过程一般指在最末尾添加，调整堆的过程就是上升操作，将添加的数上升直到最大堆的原则

• 注意每次调整堆以后，堆的长度有变化，adjustHeap()的len是变化的

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include "header.h"
using namespace std;

int arrs[] = {9,1,2,3,4,6,7,4,8,4,6,3,4 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);

//非递归方法
//调整堆过程、实际是一个下沉过程
void adjustHeap1(int * arrs, int p, int len){
    int curParent = arrs[p];
    int child = 2* p + 1;   //左孩子 需要从0开始，左孩子就是2n+1
    while(child < len){     //没有孩子
        if(child+1<len&&arrs[child]<arrs[child+1]){
            child++;    //较大孩子的下标
        }
        if(curParent<arrs[child]){
            arrs[p]=arrs[child];
            //没有将curParent赋值给孩子是因为还要迭代子树，
            //如果其孩子中有大的，会上移，curParent还要继续下移。
            p=child;
            child=2*p+1;
        }
        else
            break;
    }
    arrs[p]=curParent;
}
//调整堆的递归方法
void adjustHeap(int * arrs, int p, int len){
    int left = 2*p+1;
    int right =left+1;
    int largest =p;
    if(left<len&&arrs[left]>arrs[largest]){
        largest = left;
    }
    if(right<len&&arrs[right]>arrs[largest]){
        largest = right;
    }
    if(largest !=p){
        int temp = arrs[p];
        arrs[p] = arrs[largest];
        arrs[largest] = temp;
        adjustHeap(arrs,largest,len);
    }
}

void heapSort(int * arrs, int len){
    //建立堆，从最底层的父节点开始
    //大值上升的过程，一层一层的上升
    //调整堆变成最大堆
    for(int i = arrLen /2 -1; i>=0; i--)
        adjustHeap(arrs, i, arrLen);
    //删除最大点，然后进行下沉
    for(int i = arrLen -1; i>=0; i--){
        int maxEle = arrs[0];
        arrs[0] = arrs[i];
        arrs[i] = maxEle;
        adjustHeap(arrs, 0, i);
    }
}

//最大堆的删除操作、删除根节点
//下沉过程
//返回新的长度
int deleteHeap(int * arrs,int len){
    if(len==0) return 0;
    arrs[0] = arrs[len-1];
    adjustHeap(arrs,0,len-1);
    return len-1;
}


//最大堆的插入操作、插在末尾
//上升过程
//返回新的长度
int insertHeap(int * arrs,int len,int childValue){
    int parent = len/2 -1;
    int child = len;
    while(childValue>arrs[parent]){
        arrs[child] = arrs[parent];
        arrs[parent] = childValue;
        child = parent;
        parent = parent/2-1;
        if(parent<0) break;

    }
    return len+1;
}


int main()
{
    heapSort(arrs, arrLen );
    for (int i = 0; i < arrLen; i++)
        cout << arrs[i] << endl;
    return 0;
}

冒泡排序

public void bubbleSort(int a[],int len){
    for(int i=0;i<len;i++){
        for(int j=0;j<len-1-i;j++){//！！！！
            if(a[j]>a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp; 
            }
        }
    }
}