冒泡排序
思想
- 从左到右两两比较，如果逆序，则交换。
- 若数组中有N的数据项目，第一趟排序中有N-1次比较，第二趟有N-2比较。。。共有（N-1）+（N-2）+...+1=N(N-1)/2
- 所以冒泡算法需要O（N2）
public void bubbleSort() {
//每一趟都会将最大的放到数组的后面，算法不再处理已经排好序的数据
for(int i = nElems - 1; i > 1; i--) {
for(int j = 0; j < i; j++) {
if(a[j] > a[j+1]) {
swap(j, j+1);
}
}
}
}
private void swap(int l, int m) {
long temp;
temp = a[l];
a[l] = a[m];
a[m] = temp;
}
选择排序
思想
- 选择排序改进了冒泡排序，将必要的交换次数减少到O（N）
- 选择最小的放在左边，因此这个算法有序的都排列在左边
public void selectionSort() {
int out, in, min;
for(out = 0; out < nElems - 1; out++) {
min = out;
for(in = out + 1; in < nElems; in++) { //从左往右找最小值，与左边数据交换
if(a[in] < a[min]) {
min = in;
}
}
//交换
swap(out, min);
}
}
插入排序
思想
- 某一数据的左端已经排好序，让该数据出列，向左寻找大于该数据的数据，将找到的数据项后面有序数据向右移动一格，再将当前数据插入即可。
public void insertSort() {
int out, in;
for(out=1; out<nElems; out++) { //out为未排序最左端的数据
long temp = a[out]; //出列
in = out;
while(in>0 && a[in-1]>=temp) { //当未排序的数据小于左边某一数据
a[in] = a[in-1]; //向右移动
--in;
}
a[in] = temp; //插入
}
}
归并排序
思想
- 把一个数组分成两半
- 每一半再分成四分之一，反复分割下去，直到子数组只有一个数据项。
- 合并
package com.zywu.sort;
public class MergeSort {
public static void main(String[] args) {
int[] a = { 22, 44, 11, 55, 66, 2323, 5454};
MergeSort.mergeSort(a);
for(int i:a){
System.out.print(i + " ");
}
}
private static void mergeSort(int[] a) {
sort(a, 0, a.length-1);
}
private static void sort(int[] a, int left, int right) {
if(left==right) //划分到单个数字，不需要排序
return;
int mid = (left + right) / 2;
sort(a, left, mid); // 递归对左半部分进行分解
sort(a, mid+1, right); // 递归对右半部分进行分解
merge(a, left, mid, right); // 分解完成后进行合并
}
private static void merge(int[] a, int left, int mid, int right) { //合并算法 相当于两个数组合并
int[] temp = new int[a.length];
int i = left;
int j = mid + 1;
int k = 0;
while(i<=mid && j<=right) { // 依次比较左右数据大小，从小到大赋予新数组中
if(a[i]<a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while(i<=mid) { // 上述while执行完毕后如果i<=mid，说明左边还有剩余，直接赋给temp
temp[k++] = a[i++];
}
while(j<=right) { // 上述while执行完毕后如果j<=right，说明右边还有剩余，直接赋给temp
temp[k++] = a[j++];
}
for(int t=0; t<k; t++) { // 合并完成后将有序数组复制到原数组a[]中
a[left+t] = temp[t];
}
}
}
快速排序
思路
- 选序列第一个数作为基准数
- 先从右往左找小于基准数的数，再从左往右找大于基准数的数。交换它们
- 继续，交换。直到相遇。交换基准数和相遇数。
- 此时基准数左边数小于基准数，右边大于基准数。
- 同样方法递归处理左右边数。
package com.zywu.sort;
public class QuickSort {
public static void main(String[] args) {
int[] a = { 22, 44, 11, 55, 66, 2323, 5454};
sort(a,0, a.length-1 );
for(int i : a)
System.out.println(i);
}
private static void sort(int[] a, int low, int high) {
if(low < high) {
int result = partition(a, low, high);
sort(a, low, result-1);
sort(a, result+1, high);
}
}
private static int partition(int[] a, int low, int high) {
int key = a[low]; // 第一个数作为key，将数组划为两部分
while(low < high) { // 左右未相遇
while(low < high && a[high] >= key) // 先从数组右边往前寻找第小于key的数（必须从右开始），交换
high --;
a[low] = a[high];
while(low < high && a[low] <= key) // 再从左往右找大于key的数，交换
low ++;
a[high] = a[low];
}
a[low] = key; // key放在合适的位置，其左边都小于key，右边都大于key
return low;
}
}