java 常用排序算法，简单排序

1.冒泡排序

     基本思路是：搜索整个值列，比较相邻元素，如果两者的相对次序不对，则交换它们，其结果是最大值“像水泡一样”移动到值列的最后一个位置上，这也是它在最终完成排序的值列中合适的位置。然后再次搜索值列，将第二大的值移动至倒数第二个位置上，重复该过程，直至将所有元素移动到正确的位置上。

     时间复杂度O(n²)，最佳情况是已排好序只比较n-1次，不用交换。

  

int[] bubbleSort(int[] a) {
		//每个都进行冒泡(一个一个来)
		for (int i = 0; i < a.length; i++) {
 
			//和前n-i个比较，把最大的数沉下去
			int temp;
			for (int j = 0; j < a.length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					//交换
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}
		return a;
	}

 2.选择排序 

    基本思想：搜索整个值列，以找到最小值。将该值与值列中第一个位置上的值进行交换。搜索剩下的值列（第一个除外），以找到其中的最小值，然后将其与值列中第二个位置上的值进行交换。对值列中的每个位置重复该过程。在算法结束时，就完成了对值列的排序

   选择排序改进了冒泡排序，将必要的交换次数从O(n2)减少到O(n),比较次数仍为O(n2).

    

int[]  selectionSort(int []a){ 
		   
		for (int i = 0; i < a.length - 1; i++) {
			int min = i;
			// Find smallest name
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min]) // 找到最小值 注意此处不是判断a[j]<a[i]
					min = j;
			}
			// Swap data if necessary
			if (min != i) {
				int temp = a[i];
				a[i] = a[min];
				a[min] = temp;
			}
		}
		return a;
	}

 

3 插入排序

      基本思想：排序值列中的前2个值，并在必要时交换它们。在相对于前2个值（有序的）的适当位置插入值列的第三个值。然后，在相对于前3个值（有序的）的适当位置插入值列的第4个值。每进行一次插入操作，有序子集中的数值个数将递增1。重复该过程，直至值列中的所有值都按照次序排列为止。插入过程需要移动数组中的其他值，为插入的元素腾出存储空间。

      在大多数情况下，它比冒泡排序快一倍，比选择排序快一些，仍需O(n2)时间。常被用在比较复杂的算法的最后阶段，比如快速排序。

      

 

int[] insertionSort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int temp = a[i];
			int j = i;
			while (j > 0 && temp < a[j - 1]) {
				a[j] = a[j - 1];//all larger elements are moved one pot to the right
				j--;
			}
			a[j] = temp;
		}
		return a;
	}

   

 4 快速排序

 5堆排序

  6 几种排序的比较

        一般不太使用冒泡排序，然而当数据量小时，他会有些应用价值。

        选择排序虽然可以把交换次数降到最低，但比较的次数仍然很大。当数据量很小，并且交换数据相对于比较数据更加耗时，可以使用。

        在大多数情况下，假设数据量较小或基本有序时，插入排序是三种中最好的选择。对于更大数据量的排序来说，快速排序是更好的选择。