七大排序算法(冒泡,选择,插入,希尔,快速,合并,堆排序)的java实现

2020-11-25 03:39

阅读:945

标签:排序算法   合并   堆排序   java   希尔排序   

冒泡排序

思路:就是每次将最大或最小的元素放到数组的最后,so easy!时间复杂度为(O(n^2))
public class BubbleSort {
	public static void bubbleSort(int[] a) {
		for (int j = 1; j  a[i + 1]) {
					int temp = a[i];
					a[i] = a[i + 1];
					a[i + 1] = temp;
				}
			}
		}
	}
	public static void main(String[] args) {
		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7, 2, 3, 0, 43, 23, 12, 4, 1, 15, 7,
				3, 8, 31 };
		bubbleSort(a);
		for(int i = 0; i 

选择排序

思路:类似于冒泡,每次将后面最小的元素放在前面。时间复杂度为((O(n^2)))
public class SelectSort {
	public static void selectSort(int[] a) {
		int min;
		for (int i = 0; i  a[j]) {
					int temp = a[min];
					a[min] = a[j];
					a[j] = temp;
				}
			}
		}
	}

	public static void main(String[] args) {
		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
		selectSort(a);
		for (int i = 0; i 

插入排序

思路:从第二个元素开始,和之前的已排好序的字数组的元素比较,找到合适的位置,然后后面的元素向后移动一位,再将该元素插入到前面合适的位置。时间复杂度为(O(n^2))
public class InsertSort {
	public static void insertSort(int[] a) {
		for (int i = 1; i = 0 && a[j] > key) {
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = key;
		}
	}
	
	public static void main(String[] args) {
		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
		insertSort(a);
		for (int i = 0; i 

希尔排序

思路:类似于插入排序,只是每次所取的步长为(数组的长度 /  2 / i)。时间复杂度为(n*log n)。
public class ShellSort {
	public static void shellSort(int[] a) {
		for (int gap = a.length / 2; gap > 0; gap /= 2)
			for (int i = gap; i = 0 && a[j] > key) {
					a[j + gap] = a[j];
					j -= gap;
				}
				a[j + gap] = key;
			}

	}

	public static void main(String[] args) {
		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
		shellSort(a);
		for (int i = 0; i 

快速排序

思路:关键在于求出partition()函数。我给出了两种方法:1、从前到后。2、从前到中间,从后到中间。时间复杂度为(n * log n)最坏情况为
OK!show your my codes!
public class QuickSort {
	
	/*public static int partition(int[] a, int p, int r) {
		int x = a[r];
		int i = p - 1;
		for (int j = p; j = x && i

合并排序

思路:用分治的思想,将数组分至最小,再合并即可,不懂自己google吧!时间复杂度为(n * log n )是一个稳定的排序算法。
public class MergeSort {
	public static void merge(int A[], int p, int q, int r) {
		int[] L = new int[q - p + 1];
		int[] R = new int[r - q];
		for (int i = p, j = 0; i 

堆排序

思路:建立一个堆,大顶堆或者小顶堆都可以。每次将堆顶元素放到数组最后,然后堆的规模减小一个,再维持第一个元素的大顶堆性质。时间复杂度为(n * log n)。
public class HeapSort {
	//求双亲位置
	static int parent(int i) {
		return i / 2;
	}
	//求左孩子位置
	static int left(int i) {
		return 2 * i;
	}
	//求右孩子位置
	static int right(int i) {
		return 2 * i + 1;
	}
	//维持大顶堆的性质
	static void maxHelpify(int[] A, int i) {
		int l = left(i);
		int r = right(i);
		int largest = 0;
		if (l  A[i])
			largest = l;
		else
			largest = i;
		if (r  A[largest])
			largest = r;
		if (largest != i) {
			int temp = A[largest];
			A[largest] = A[i];
			A[i] = temp;
			maxHelpify(A, largest);
		}
	}
	//建立大顶堆
	static void buildMaxHeap(int[] A){
		for(int i=(A.length-1)/2; i>0; i--){
			maxHelpify(A, i);
		}
	}
	//堆排序
	public static void heapSort(int[] A){
		buildMaxHeap(A);//建立大顶堆
		//每次把堆顶的数放到数组最后,然后把堆的大小减1,再次维持第一个数的大顶堆性质
		for(int i = A.length - 1; i>=2; i--){
			int temp = A[1];
			A[1] = A[i];
			A[i] = temp;
			A[0]--;
			maxHelpify(A, 1);
		}
	}
	public static void main(String[] args) {
		int A[] = new int[3];
		A[0] = A.length-1;//a[0]存放堆的大小
		for(int i = 1; i 

其他:还有一种计数排序。

比较简单:就是将数组下标作为元素的value,特殊情况下使用。如排序N个人的年龄就可以用计数排序。将年龄看作数组的下标,定义一个大小为100的数组,将年龄与之比较,如果年龄==下标就将,该下标的value+1.时间复杂度为(N)。





















七大排序算法(冒泡,选择,插入,希尔,快速,合并,堆排序)的java实现

标签:排序算法   合并   堆排序   java   希尔排序   

原文地址:http://blog.csdn.net/dafeng_blog/article/details/24807545


评论


亲,登录后才可以留言!