赞
踩
按照排序过程中所依据的原则的不同可以分类为:
►插入排序:直接插入排序 希尔排序
►交换排序:冒泡排序 快速排序
►选择排序:简单选择排序 堆排序
►归并排序
►基数排序
从平均情况看:堆排序、归并排序、快速排序胜过希尔排序。
从最好情况看:冒泡排序和直接插入排序更胜一筹。
从最差情况看:堆排序和归并排序强过快速排序。
虽然直接插入排序和冒泡排序速度比较慢,但是当初始序列整体或局部有序是,这两种算法的效率比较高。当初始序列整体或局部有序时,快速排序算法效率会下降。当排序序列较小且不要求稳定性是,直接排序效率较好;要求稳定性时,冒泡排序法效率较好。
8大排序算法:插入、冒泡、选择、希尔、归并(外部)、快速、堆、基数
内部排序:排序期间,元素全部放在内存中的排序
外部排序:排序期间,元素无法全部存放在内存中,必须在排序过程中根据要求不断地进行内外存之间移动排序
稳定性:指的是经过排序后,值相同的元素保持原来顺序的相对位置不变
1.冒泡排序:(全部按照升序排列)
思想:从第一个数开始,两两比较,如果第二个数比第一个数大,交换第一个数与第二个数的位置,相当于大泡泡往下沉了,一趟完了之后,最大的那个数就在最后一个位置了;然后继续比较,接下来是第二大的数字排在倒数第二个位置。。。
void BubbleSort(int arr[], int size) { for (int i = 0; i < size-1; i++) { for (int j = 0; j < size-i-1; j++) { if (arr[j]>arr[j + 1]) { int temp; temp = arr[j]; arr[j] = arr[j+1]; arr[j + 1] = temp; } } } }
2.插入排序
思想:给一组数据,先对前一个元素进行排序(就是第一个数),然后对前两个数进行排序,再对前三个数进行排序。。。。一直到排完为止。
void InsertSort(int arr[], int size) { int tmp,i,j; for (i = 1; i < size; i++) { tmp = arr[i]; for (j = i - 1; j >= 0; j--) { if (tmp < arr[j])//如果第二个数比第一个数大的话,就要交换 { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = tmp; } }
3.希尔排序
希尔排序是在直接插入排序的基础上进行的改进:
1)首先计算整个数组大小,然后除以2,比如说原始数组中有8个元素,除以2之后那么跨度就是4,第1个元素和跨度为4的元素为一组,第2个元素与跨度为4的元素为一组,以此类推。这样下来,就会是两两一组,一共有4组,每组进行排序。
2)然后跨度为2,重复第1)步的过程
3)然后跨度为1,重复第1)步的过程
示例中所使用的分组跨度(4,2,1),被称为希尔排序的增量,增量的选择可以有很多种,我们在示例中所用的逐步折半的增量方法,是Donald Shell在发明希尔排序时提出的一种朴素方法,被称为希尔增量。
void ShellSort(int arr[], int size) { int i, j,tmp,h; for (h = size / 2; h > 0; h /= 2) { for (i = h; i < size; i++) { tmp = arr[i]; for (j = i - h; j>=0; j-=h) { if (tmp < arr[j]) { arr[j + h] = arr[j]; } else { break; } } arr[j + h] = tmp; } } }
4.快速排序
算法思想:
分治法:比大小,再分区
1.从数组中选择一个数作为基准数,通常选择的是第一个数
2.分区:把比基准数小的数放在基准数的左边,把比基准数大的数放到基准数的右边。
3.再对左右区间重复第二步,直到区间中只有一个数。
实现思路:
挖坑填数
1.将基准数挖出形成第一个坑
2.由后向前找出比它小的数,找到后挖出此数填到前一个坑中
3.由前向后找比它大或等于的数,找到后挖出此数填到前一个坑中
4.重复2,3两步。
【5,3,9,1,6,7,2,4,0,8】
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 5 3 9 1 6 7 2 4 0 8
坑位 坑位1 坑位3 坑位5 坑位7 坑位6 坑位4 坑位2
0 4 2 5 7 6 9
0 3 4 1 2 5 7 6 9 8
通俗解释:就是先找一个基准数,通常是第一个数,然后把这个数对应的位置置为坑位1,然后先在右边找比基准数小的数,找到之后,把它对应的位置置为坑位2,然后把空位2的数放到坑位1中。然后从左边找比基准数大的数,找到的话记为坑位3,把坑位3的数,放到坑位2中。。。一直重复这个动作,最后只剩下一个坑位的时候,把基准数放到那个坑位中,这样就会使得基准数左边都是比它小的数,基准数的右边都是比它大的数。
这样的话,就是需要两个循环,分别是从左往右的循环和从右往左的循环。
void QuickSort(int arr[],int left, int right) { int tmp, tmp2; int i, j; i = left; j = right; if (left >= right) { return; } int base = arr[left]; while (i < j) { while (arr[j]>=base&&i<j)//从右向左找如果比基准数大的话,就往前移一个,如果比基准值小就挖坑 { j--; } while (arr[i] <= base&&i<j)//从左往右找,如果比基准数小的话,就往后移一个,如果比基准数大的就挖坑 { i++; } if (i < j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } tmp2 = arr[i]; arr[i] = arr[left]; arr[left] = tmp2; QuickSort(arr,left, i - 1); QuickSort(arr, i + 1, right); }
5.选择排序
遍历数组,每次把最大的一个元素放到最后一个位置,直到还剩下一个数字,此时数组就是有序的。
void SelectSort(int arr[], int size) { int i, j; for (i = size; i > 1; i--) { int max = 0; for (j = 0; j < i; j++) { if (arr[j]>arr[max]) { max = j; } } int tmp = arr[i - 1]; arr[i - 1] = arr[max]; arr[max] = tmp; } }
6.归并排序
归并排序的核心思想在于“分治”,所谓“分治”就是分而治之,把一个大的问题划分为许多小问题去解决,在处理数组排序时,如果数组中只有一个元素,那么我们就可以认为这个数组就是有序的,如果数组中有两个元素,那么最多只需比较一次就可得到排好序的数组,这就是分治算法的核心
归并排序就是,假设我们要排【3,2,5,1,4】这个数组,那么一般按照前原数组分成两部分的思想,这里可把原数组分成【3,2,5】和【1,4】然后可以继续分,直到分到单个元素为止
。
显然这个过程可以分为两个部分:
1.拆分过程:很明显适合使用递归写法,具体就是数组大小除2,一直这样,直到数组中元素个数为1
2.合并过程。
合并过程可分为3个部分,首先是把原数组分为左数组和右数组。第二部分就是根据大小进行拍戏,如果左数组中的元素大小小于右数组元素大小,就把左数组中元素放入数组中,反之将右数组中的元素放入数组中。第三部分:比较之后,可能左数组和右数组中有剩余的元素,将数组中剩余的元素放入数组中就可得到有序的数组。
void Divide(int arr[], int start, int end) { while (start >= end) { return; } int mid = (start + end) / 2; Divide(arr, start, mid); Divide(arr, mid + 1, end); } void MergeSort(int arr[], int start, int mid, int end)//这块是合并过程 { //第一部分是将原数组中的元素分别存在左数组和右数组中 int left[256] = { 0 };//左数组 int right[256] = { 0 };//右数组 int leftsize = mid - start + 1; int rightsize = end - mid; for (int i = 0; i < leftsize; i++) { left[i] = arr[i]; } for (int j = 0; j < rightsize; j++) { right[j] = arr[j]; } //第二部分主要是比较大小了 int i=0, j=0, k=0; for (k = start; i < leftsize&&j < rightsize; ++k) { if (left[i] < right[i]) { arr[i] = left[i]; i++; } else { arr[j] = right[j];//i和j的范围之和就是整个数组的大小,因此不会出现覆盖的情况 j++; } } //第三部分就是把左数组和右数组中剩下的元素放到arr中 if (i < leftsize)//如果左数组中元素有剩余 { for (; i < leftsize; i++) { arr[i] = left[i]; ++k; } } if (j < rightsize)//如果右数组中元素有剩余 { for (; j < rightsize; j++) { arr[j] =right[j]; ++k; } } }
7.堆排序
主要要依据堆结构,堆是一种具有特殊性质的完全二叉树(就是连着排的,中间没有空的),这个特殊性质就是,如果是大堆的话,那么根结点的值要大于两个孩子结点的值。如果是小堆的话,那么根节点的值要小于左右孩子结点的值。
【5,2,7,3,6,1,4】
思路:就是不断调整结点的位置,如果是升序的话,就调整成大堆的形式,调整成大堆的形式之后,此时堆顶元素就是最大的一个,取出堆顶的元素放到数组中的最后一个位置,此时堆顶就会空出一个位置,然后把二叉树的最后一个位置的元素放到堆顶,然后继续调整,使之成为一个大堆,然后取出堆顶元素,一直取,直到剩余一个元素,此时数组中就是一个升序序列。
写代码的时候,分成两个部分,首先要建堆,建堆的过程就是从最后一个非叶子结点开始向上调整,因为叶子结点最终都是要放到根节点的,所以就不用从叶子结点开始了,当然从叶子结点开始也是可以的,调整完了之后,将最后一个叶子结点与根节点进行交换,交换完了还得调整,因为可能此时已经不满足堆的性质了。
第二部分是具体的向上调整的过程:
这里有几点:
如果当前要访问的结点索引为i的话,那么
父节点索引:(i-1)/2
左孩子索引:2i+1;
右孩子索引:2i+2;
首先要判断如果左孩子索引小于数组大小,说明没调整完,如果左孩子数值大于最大索引位置的数值是,要把左孩子索引赋值给最大值索引。同理,右孩子也是一样。完了之后,如果发现此时最大值索引是不等于传入那个索引,也就是根节点索引的时候,说明需要交换位置了,就把最大值索引结点值与arr[index]值进行交换,交换完了再调整(只要交换了,就需要调整)
void UpAdjust(int arr[], int index, int size) { int leftchild = 2 * index + 1; int rightchild = 2 * index + 2; int maxindex = index; if (leftchild < size&&arr[maxindex] < arr[leftchild]) { maxindex = leftchild; } if (rightchild < size&&arr[maxindex] < arr[rightchild]) { maxindex = rightchild; } if (maxindex != index) { swap(arr[maxindex], arr[index]); UpAdjust(arr, maxindex, size); } } void HeapSort(int arr[], int size) { for (int i = size - 1; i >= 0; i--) { UpAdjust(arr, i, size); } for (int i = size-1; i >= 0; i--) { swap(arr[0], arr[i]); UpAdjust(arr, 0, i); } }
8.基数排序
就是比如说一组数据【73,22,93,43,55,14,28,65,39,81】
先按照个位排序:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
然后把这些重新排序起来【81 22 73 93 43 14 55 65 28 39】
按照十位排序:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
然后把这些排序起来【14 22 28 39 43 55 65 73 81 93】
int maxbit(int data[], int n) { int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d; } void radixsort(int data[], int n) //基数排序 { int d = maxbit(data, n); int tmp[n]; int count[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //进行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。