冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
设数组长度为N
Shell
static void BubbleSort(int a[],int n){ int i, j; for (i = 0; i < n; i++) { for (j = 1; j < n-1; j++) { if(aj-1 >aj){ Swap(a, j, j-1); } } } }
12345678910 | static void BubbleSort(int a[],int n){ int i, j; for (i = 0; i < n; i++) { for (j = 1; j < n-1; j++) { if(aj-1 >aj){ Swap(a, j, j-1); } } }} |
---|
我们设置一个 flag,如果这一趟发生了交换,则为 true,否则为 false。明显如果有一趟没有发生交换,说明排序已经完成。
Shell
static void BubbleSort2(int a[],int n){ int j ,k; boolean flag; k = n; flag = true; while(flag){ flag = false; for (j = 1; j < k; j++) { if (aj-1 > aj) { Swap(a, j, j-1); flag = true; } } k--; } }
12345678910111213141516171819 | static void BubbleSort2(int a[],int n){ int j ,k; boolean flag; k = n; flag = true; while(flag){ flag = false; for (j = 1; j < k; j++) { if (aj-1 > aj) { Swap(a, j, j-1); flag = true; } } k--; }} |
---|
我们会出现这么一种情况,假设有 100 个数字,只有前 10 个无序,后面的 90 个全部都有序,那么我们就不需要每次都要往后遍历,只需要遍历到需要最后一次交换的位置即可。
Shell
static void BubbleSort3(int a[],int n){ int j ,k ; int flag; flag = n; while(flag > 0){ k = flag; flag = 0; for (j = 1; j < k; j++) { if(aj-1 > aj){ Swap(a, j, j-1); flag = j; } } } }
123456789101112131415161718 | static void BubbleSort3(int a[],int n){ int j ,k ; int flag; flag = n; while(flag > 0){ k = flag; flag = 0; for (j = 1; j < k; j++) { if(aj-1 > aj){ Swap(a, j, j-1); flag = j; } } }} |
---|
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
Shell
public int AdjustArray(int s[],int l,int r){ int i = l,j = r; int x = sl; //si 即si 就是一个坑 while(i < j){ while(i < j && sj >= x){ j--; } if(i < j){ si = sj; i++; } //从左向右找大于或等于x的数来填sj while(i < j && si < x){ i++; } if(i < j){ sj = si; j--; } } //结束之后 i等于j si = x; return i; } void quick_sort01(int s[],int l,int r){ if(l < r){ int i = AdjustArray(s, l, r); quick_sort01(s, l, i-1); quick_sort01(s, i+1, r); } }
1234567891011121314151617181920212223242526272829303132333435 | public int AdjustArray(int s[],int l,int r){ int i = l,j = r; int x = sl; //si 即si 就是一个坑 while(i < j){ while(i < j && sj >= x){ j--; } if(i < j){ si = sj; i++; } //从左向右找大于或等于x的数来填sj while(i < j && si < x){ i++; } if(i < j){ sj = si; j--; } }//结束之后 i等于j si = x; return i; } void quick_sort01(int s[],int l,int r){ if(l < r){ int i = AdjustArray(s, l, r); quick_sort01(s, l, i-1); quick_sort01(s, i+1, r); } } |
---|
Shell
void quickSort(int s[],int l,int r){ if(l < r){ int i = l;int j = r; int x = sl; while(i < j){ while(i < j && x <= sj){ //从右向左找第一个小于x的数 j--; } if(i < j){ si++ = sj; } while(i < j && x > si ){ //从左向右找第一个大于等于x的数 i++; } if(i < j){ sj-- = si; } } si = x; quickSort(s, l, i-1);//递归调用 quickSort(s, i+1, r); } }
12345678910111213141516171819202122232425 | void quickSort(int s[],int l,int r){ if(l < r){ int i = l;int j = r; int x = sl; while(i < j){ while(i < j && x <= sj){ //从右向左找第一个小于x的数 j--; } if(i < j){ si++ = sj; } while(i < j && x > si ){ //从左向右找第一个大于等于x的数 i++; } if(i < j){ sj-- = si; } } si = x; quickSort(s, l, i-1);//递归调用 quickSort(s, i+1, r); }} |
---|
选择排序 (Selection-sort) 是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下:
Shell
static void SelectSort(int a[],int n){ for (int i = 0; i < n; i++) { int key = i; int min = ai; for (int j = i; j < n; j++) { if(min > aj){ min = aj; key = j; } } Swap(a, i, key); } }
12345678910111213 | static void SelectSort(int a[],int n){ for (int i = 0; i < n; i++) { int key = i; int min = ai; for (int j = i; j < n; j++) { if(min > aj){ min = aj; key = j; } } Swap(a, i, key); }} |
---|
表现最稳定的排序算法之一,因为无论什么数据进去都是 O (n2) 的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父节点到根节点必然是一个有序的数列,现在的任务就是将这个新数据插入到这个有序数据中,这就类似于直接插入排序中将一个数据插入到一个有序空间中。
Shell
void MinHeapFixup(int a[],int i) { int j, temp; temp = ai; j = (i-1)/2; //父节点 while(j >= 0 && i != 0) { if(aj < temp) { break; } ai = aj; //把较大的子结点往下移动,替换它的子节点 i = j; j = (i -1 )/2; } aj = temp; }
123456789101112131415161718 | void MinHeapFixup(int a[],int i) { int j, temp; temp = ai; j = (i-1)/2; //父节点 while(j >= 0 && i != 0) { if(aj < temp) { break; } ai = aj; //把较大的子结点往下移动,替换它的子节点 i = j; j = (i -1 )/2; } aj = temp;} |
---|
按照定义,堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根节点,然后在从根结点开始进行一次从上向下调整。调整时先在左右子树找到最小的如果父节点比这个最小的子节点还小,说明不需要调整了,反之将父节点和它交换之后再考虑后面的节点。相当于从根节点讲一个数据的下沉的过程。
Shell
//从第i个节点开始调整,n为节点的总数,从0开始计算,i节点的子节点为 2*i+2,2*i+2 void MinHeapFixDown(int a[],int i,int n){ int j ,temp; temp = ai; j = 2*i+1; while(j < n){ if(j +1 < n && aj+1 < aj)//在左右子树中查找最小的 j++; if(aj > temp){ break; } ai = aj; //将较小的子结点往上移动 替换它的父节点 i = j; j = 2 * i +1; } ai = temp; } //在最小堆中删除数 void MinHeapDelete(int a[],int n){ Swap(a, 0, n-1); MinHeapFixDown(a, 0, n-1); }
1234567891011121314151617181920212223242526 | //从第i个节点开始调整,n为节点的总数,从0开始计算,i节点的子节点为 2*i+2,2*i+2 void MinHeapFixDown(int a[],int i,int n){ int j ,temp; temp = ai; j = 2*i+1; while(j < n){ if(j +1 < n && aj+1 < aj)//在左右子树中查找最小的 j++; if(aj > temp){ break; } ai = aj; //将较小的子结点往上移动 替换它的父节点 i = j; j = 2 * i +1; } ai = temp; } //在最小堆中删除数 void MinHeapDelete(int a[],int n){ Swap(a, 0, n-1); MinHeapFixDown(a, 0, n-1); } |
---|
Shell
//建立最小堆 void MakeMinHeap(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) MinHeapFixdown(a, i, n); }
123456 | //建立最小堆 void MakeMinHeap(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) MinHeapFixdown(a, i, n); } |
---|