Snail—算法学习之内部排序
分类：数据结构与算法
说到排序 就是使得数据按照一定的规则排列起来 使得更好的对数据进行各种操作
文章的题目内部的意思就是数据量小，数据直接在内存中就可以排序
而相对来说的外部 就是需要访问外部数据了 比如网络上的、硬盘上得等等
一、交换排序—冒泡排序
//冒泡排序/*最传统的思想就是 每循环一次 把最大的那个数 冒到最后12 32 34 22 12 35 21 57 49 912 32 22 12 34 21 35 49 9 5712 22 12 32 21 34 35 9 49 5712 12 22 21 32 34 9 45 49 5712 12 21 22 32 9 34 45 49 5712 12 21 22 9 32 34 45 49 5712 12 21 9 22 32 34 45 49 5712 12 9 21 22 32 34 45 49 5712 9 12 21 22 32 34 45 49 579 12 12 21 22 32 34 45 49 57*/
void bubbleSort(int array[],int arryaLength){for (int i = 0; i < arryaLength ; i++) {for (int j = 0; j < arryaLength – i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}int main(int argc, const char * argv[]){int array[] = {12,32,34, 22, 12, 35, 21, 57, 49, 9};bubbleSort(array, 10);return 0;}
下面我们对上面的算法可以做一下改进 我们用pos来记录一下每次排序完成后的位置 让它外层循环到pos这个位置就可以了，没必要再循环到整个数组的末尾
void bubbleSort_1(int array[],int arrayLength){int i = arrayLength;while (i > 0) {int pos = 0;for (int j = 0; j < i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];pos = j;array[j + 1] = temp;}}i = pos;}}上面的这些算法 就只是 要么从小排到大 要么从大排到小 我们也可以让这两种情况同时进行void bubbleSort_2(int array[],int arrayLength){//low、high记录一下初始位置int lowIndex = 0;int highIndex = arrayLength – 1;while (lowIndex < highIndex) {for (int j = lowIndex; j < highIndex; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}lowIndex++;for (int j = highIndex; j > lowIndex; j–) {if (array[j] < array[j – 1]) {int temp = array[j];array[j] = array[j – 1];array[j – 1] = temp;}}highIndex–;}}
二、交换排序—快速排序
快速排序 是用的分治策略
可以看到下面的代码 以我的看法 就是 设置一个pk，作为基准数 一般设为数组的第一个 然后比基准数小的放到基准数的左边，大得放到基准数的右边
然后 首部a[low]，尾部a[high]
如果 a[high] > pk 那么让high–, 一直到a[high] <= pk，，然后交换a[low] 和 a[high];
然后 再从low那边进行一下排序 如果a[low] < pk 那么low++,直到a[low]>=pk,交换a[low] 和 a[high];
//快速排序void swap(int * a,int * b){int temp = *a;*a = *b;*b = temp;}int partition(int a[],int low,int high){int pk = a[low];while (low < high) {while (low < high && a[high] >= pk)high–;swap(&a[low], &a[high]);while (low < high && a[low] <= pk)low++;swap(&a[low], &a[high]);}return low;}void quickSort(int a[],int low,int high){if (low < high) {int pkIndex = partition(a, low, high);quickSort(a, low, pkIndex -1);quickSort(a, pkIndex + 1, high);}for (int i = 0; i < high; i++) {printf("%d ",a[i]);}printf("\n");}
三、选择排序—简单选择排序
拿出一个数来跟其他的数比较 直到找到满条件的 才交换一次
//选择排序void selectSort(int array[],int arrayLength){for (int i = 0; i < arrayLength – 1; i++) {for (int j = i + 1; j < arrayLength; j++) {if (array[i] > array[j]) {int temp = array[i];array[i] = array[j];array[j] = temp;}}}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇Snail—算法学习之最大公约、最小公倍下一篇Snail—iOS开发中得一些小技巧
顶0踩0
效果只能是既费时又没有胜利，再聪慧的人也没法成学。
