数据结构和算法－排序

一、简单排序

1.冒泡排序O(n^2)

两两比较，反序交换

public static int[] bubbleSort(int[] arr) {
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = 0; j < arr.length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				arr[j]   = arr[j] ^ arr[j+1];
				arr[j+1] = arr[j] ^ arr[j+1];
				arr[j]   = arr[j] ^ arr[j+1];
			}
		}
	}
	return arr;
}

2.选择排序O(n^2)

public static int[] selectSort(int[] arr) {
		int minIndex = -1;
		for (int i = 0; i < arr.length - 1; i++) {
			minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if(arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}
			if(i != minIndex) {
				arr[i]        = arr[minIndex] ^ arr[i];
				arr[minIndex] = arr[minIndex] ^ arr[i];
				arr[i]        = arr[minIndex] ^ arr[i];
			}
		}
		return arr;
	}

3.插入排序

将一个记录插入到已经排好序的有序表中得到一个新的、记录增1的有序表

public static int[] insertSort(int[] arr) {
		int sentinel;
		int index = -1;
		for (int i = 1; i < arr.length; i++) {
			sentinel = arr[i];
			if(arr[i] < arr[i - 1]) {
				// loop compare
				for (int j = 0; j < i; j++) {
					if(arr[i] < arr[j]) {
						index = j;
						break;
					}
				}
				// move
				for (int k = i; k > index; k--) {
					arr[k]   = arr[k] ^ arr[k-1];
					arr[k-1] = arr[k] ^ arr[k-1];
					arr[k]   = arr[k] ^ arr[k-1];
				}
				arr[index] = sentinel;
			}
		}
		return arr;
	}

二、复杂排序

1.希尔排序O(n^(3/2))

增量序列最后一个增量值必须等于1，初次取序列的一半为增量，以后每次减半，使序列基本有序，直到增量为1。

不实现了，在直接排序的基础上增加了一个增量，序列的增量比较。

 

2.堆排序O(nlogn)

是在选择排序基础上的改进，将序列构建成一个大顶堆，将堆顶元素移走，再将剩下的元素重新构建一个堆

堆：完全二叉树，节点大于或等于其左右节点的值称为大顶堆，小于或等于称为小顶堆

public static int[] heapSort(int[] arr) {
		int len = arr.length;
		// 构建大顶堆
		for (int i = len / 2; i > 0 ; i--) {
			adjustHeap(arr, i-1, len);
		}
		
		for (int i = len - 1; i > 0; i--) {
			// 将堆顶数据与最后一个数据交换
			arr[0] = arr[0] ^ arr[i];
			arr[i] = arr[0] ^ arr[i];
			arr[0] = arr[0] ^ arr[i];
			
			adjustHeap(arr, 0, i);
		}
		return arr;
	}
	
	// 调整堆结构
	public static int[] adjustHeap(int[] arr, int curInd, int len) {
		int tmp = arr[curInd];
		// 当前节点与其自节点比较交换 子节点：2*curIndex 2*curIndex+1 
		for(int i = (curInd + 1) * 2; i <= len; i++) {
			// 判断左右节点大小，将i设置为较大值index
			if (i < len && arr[i-1] < arr[i]) {
				++i;
			}
			
			// 父节点与较大子节点比较
			if (arr[curInd] > arr[i-1]) {
				break;
			}
			arr[curInd] = arr[curInd] ^ arr[i-1];
			arr[i - 1]  = arr[curInd] ^ arr[i-1];
			arr[curInd] = arr[curInd] ^ arr[i-1];
			curInd = i - 1;
		}
		arr[curInd] = tmp;
		return arr;
	}

 

 3.归并排序

用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列

 

public static int[] mergeSort(int[] arr, int first, int last) {
		if ((first + 1) < last) {
			int mid = (first + last) / 2;
			mergeSort(arr, first, mid);
			mergeSort(arr, mid, last);
			merge(arr, first, mid, last);
		}
		return arr;
	}
	
	public static void merge(int[] arr, int first, int mid, int last) {
		int[] tmp = new int[last - first];
		int indexL = first, indexR = mid, index = 0;
		
		while(indexL < mid && indexR < last) {
			if (arr[indexL] < arr[indexR]) {
				tmp[index] = arr[indexL];
				indexL ++;
			} else {
				tmp[index] = arr[indexR];
				indexR ++;
			}
			index ++;
		}
		
		while (indexL < mid) {
			tmp[index] = arr[indexL];
			index ++;
			indexL ++;
		}
		
		while (indexR < last) {
			tmp[index] = arr[indexR];
			index ++;
			indexR ++;
		}
		
		index = 0;
		for (int i = first; i < last; i++) {
			arr[i] = tmp[index];
			index ++;
		}
		
	}

 

 4.快速排序O(nlogn)

经过一次排序分割成2部分，一部分大于另一部分

public static int[] quickSort(int[] arr, int low, int high) {
		int privot;
		if (low < high) {
			privot = partition(arr, low, high);
			quickSort(arr, low, privot - 1);
			quickSort(arr, privot + 1, high);
		}
		return arr;
	}

	public static int partition(int[] arr, int low, int high) {
		int privotKey = arr[low];
		while (low < high) {
			while (low < high && privotKey <= arr[high]) {
				high--;
			}
			swap(arr, low, high);
			while (low < high && privotKey >= arr[low]) {
				low++;
			}
			swap(arr, low, high);
		}
		return low;
	}

	public static void swap(int[] arr, int i1, int i2) {
		if (i1 != i2) {
			arr[i1] = arr[i1] ^ arr[i2];
			arr[i2] = arr[i1] ^ arr[i2];
			arr[i1] = arr[i1] ^ arr[i2];
		}
	}

 优化：随机选取、三数取中