排序 - notSherry

@(刷题生活)

排序方法

选择排序：低效，n平方`` 不稳定

扫描整个列表找出最小值，将它与列表第一个位置的值交换扫描剩余部分的列表，找出最小值，与该列表第二个位置处的值交换对列表中的每一个位置继续使用该过程

插入排序 ：低效 n平方 稳定

对列表的头两个值进行排序，将第三个值插入到前两个值的恰当位置，将第四个值插入到列表前三个值的恰当位置......

void insertSort(int data[],int len){
    for(int index = 1;index < len;index++){
        int key = data[index];
        int position = index;
        while(position > 0&& data[position-1] > key){
            data[position] = data[position -1];
            position--;
        }
        data[position] = key;
    }
}

冒泡排序：低效 n平方 稳定

扫描列表邻接元素，如果不是按照相对顺序排列则将他们交换，每经过一轮，冒泡排序算法都会将最大值移到最终的位置

快速排序：高效 nlogn 不稳定

是所有排序算法中最高效的一种，采用了分治的思想：先保证列表的前半部分都小于后半部分，然后再对前半部分和后半部分排序，这样整个列表就有序了。

void quickSort(int data[],int low,int high){
    if(low < high){
        //create partition
        int indexofpartition = partition(data,min,max);
        //sort the left partition
        quickSort(data,min,indexofpartition - 1);
        //sort the right partition
        quickSort(data,indexofpartion + 1,max);
    }
}



int partition(int data[],int low,int high){
    int partitiononelement;
    int left,right;
    int middle = (min + max)/2;
     //using the middle data as the partition element
    partitiononelement = data[middle];
    swap(data,middle,low);
    left = low;
    right = high;

    while(left < right){
        //search an element that is big than the partition element
        while(left<right&&data[left]<=partitiononelement){
            left++;
        }
        //search an element that is small than the partition element
        while(data[right]>partitiononelement){
            right--;
        }
        if(left < right){
            swap(data,left,right);
        }
    }
    swap(data,low,right);
    return right;
}

void swap(int data[],int a,int b){
    int tmp;
    tmp = data[a];
    data[a] = data[b];
    data[b] = tmp;
}

归并排序（merge sort） nlog2n最坏 稳定

将列表分成两个大约相等的部分，对每一个部分递归调用其自身。继续该列表的递归分解，直至达到该递归的基本情形，这时该列表被分割成长度为1的列表，然后随着程序控制权传回至该递归调用结构，该算法将两个递归调用所产生的那两个排序子列表归并为一个排序列表。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。若要求排序稳定，则可选用归并排序。

查找

线性顺序查找

二分查找

int Search(int a[],int key,int len){
    int low = 0,hight = len - 1,mid;
    while(low <= high){
        mid = (low+high)/2;
        if(a[mid] == key) return mid;
        else if(a[mid]<key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;      //没有找到的时候  
}

哈希查找 哈希查找的操作步骤：

1) 用给定的哈希函数构造哈希表；

2) 根据选择的冲突处理方法解决地址冲突；

3) 在哈希表的基础上执行哈希查找。

Hash表检索数据
int searchHash(int hash[],int hashLength,int key){
    int hashAddress = key%hashLength;
    if(hash[hashAddress]!=0&&hash[hashAddress]!=key){
        hashAddress = (++hashAddress)%hashLength;
    }
    if(hash[hashAddress] == 0){
        return -1;
    }
    else{
        return hashAddress;
    }
}


//数据插入hash表

void insertHash(int hash[],int hashLength,int data){
    int hashAddress = data%hashLength;
    while(hash[hashAddress]!=0){
        //用开放寻址找
        hashAddress = (++hashAddress)%hashLength;
    }
    hash[hashAddress] = data;
}

tips - strlen可以用来求字符数组的长度，不可以用来求整数数组的长度，它是找到’\0’来标记结束，但是整数的0就会是’\0’ - sizeof(data)/sizeof(int)求的是数组长度。如data[200]求出来就是200，不会在意里面真实有多少。