文章目录
- 直接插入排序
- 希尔排序
- 选择排序
- 冒泡排序
- 快速排序
- 归并排序
- 计数排序
直接插入排序
思想：
/**
* 直接插入排序
* 具有稳定性
* 时间复杂度为：（计算时间复杂度的时候应计算执行次数最多的语句类，在直接插入排序中次数最多的语句为比较语句（每一个元素与其前面有序的数据进行比较）
* 最好情况下O(n) ,最坏情况下O(n^2)
* 空间复杂度为：O(1);
*/
public void insertSort(int[] array) {
//直接插入排序
//思想：前面的数据看作有序的，依次遍历后面的数据群，将其插入到前面的数据群中去，使得前面的数据群变为有序
//当所有的乱序元素遍历完时，整个数组直接插入排序完成。
for (int i = 1; i < array.length; i++) {
//比较乱序数组的第一个元素与有序数组的每个元素，直到下标为0为止。
int tmp = array[i];
//指向乱序的数组下标与指向有序数组下标是有关联的，所以用一个变量表示即可
int j = i - 1;
for (; j >= 0; j--) {
//当数组改变时，其对应下标的值也会改变
//当乱序的元素比有序的元素的值小时
if (tmp < array[j]) {
array[j + 1] = array[j];
//此时还需判断一下
/* if(j ==0){
array[j] =tmp;
sortend++;
}*/
} else {
array[j + 1] = tmp;
break;
}
}
//当执行到此时,j 是0还是-1？是 - 1
//当乱序的元素插入到有序元素的中间时，这条语句的执行会不会出现错误？
//此种情况下j不为-1.
array[j + 1] = tmp;
}
}
希尔排序
注：gap的增量序列怎样变化才能致使在排序过程中元素之间的比较次数最少，还没有真正的定论，在此次实现中，取gap 初始值 = array.length/2 ,且gap =gap/2来实现gap的增量变化序列。
希尔排序的思想：
public void shellsort(int[] array) {
//希尔排序
//将每次分组后的数据进行调整，根据gap进行分组
for (int gap = array.length / 2; gap >= 1; gap = gap / 2) {
//当gap ==1时，每一个元素会不会与前面的元素进行比较？
//当某一个元素在两个分组中，自
shell(array, gap);
}
}
private void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
//比较乱序数组的第一个元素与有序数组的每个元素，直到下标为0为止。
int tmp = array[i];
//指向乱序的数组下标与指向有序数组下标是有关联的，所以用一个变量表示即可
int j = i - gap;
for (; j >= 0; j-=gap) {
//当数组改变时，其对应下标的值也会改变
//当乱序的元素比有序的元素的值小时
if (tmp < array[j]) {
array[j + gap] = array[j];
} else {
array[j + gap] = tmp;
break;
}
}
array[j + gap] = tmp;
}
}
选择排序
思想： 即每一次从待排序序列中选出一个最小（或最大的元素数据），存放在序列的起始位置，直到所有的数据均排序完。
选择排序1：
public void selectSort1(int[] array) {
//每次挑选出一个最小的数据，放在小下标处，总共挑选array.length-1次
for (int k = 0; k < array.length-1; k++) {
// 不存储数据，存储下标
int tmp =k; //令最小的数据的下标为tmp
for (int i = k+1; i < array.length; i++) {
if (array[i] < array[tmp]) {
tmp = i;
}
}
swap(array,tmp,k);
}
}
private void swap(int[] array,int x,int y){
int tmp = array[x];
array[x] =array[y];
array[y] =tmp;
}
选择排序2：
实现思想：每次遍历一遍即将待排序序列的最小值与最大值放在序列的下标最小与最大处，
在设定待排序序列的最小值下标与最大值下标均为left，然后再遍历过程中，遇到小于当前最小值的下标时，则替换下标，最大值亦是如此，遍历一遍，然后待排序序列从左右均收缩一个元素。继续上述步骤，直到left>=right
/**
* 选择排序2：
* 思想：对第一个选择排序思想的优化，上一个思想只是在一端开始进行放置有序数据
* 可以在两端分别放置最大与最小的数据
*
* @param array
*/
public void selectsort2(int []array){
int left = 0;
int right = array.length-1;
while (left<right){
int minIndex = left;
int maxIndex = left;
//问题，怎样获取最大值与最小值？
//遍历中间区间，逐渐获取小与大的数据
for (int i = left; i <=right ; i++) {
if(array[i+1]<array[minIndex]){
minIndex = i ;
}
if(array[i+1]>array[maxIndex]){
maxIndex = i;
}
}
// 如果最大值是left下标，在交换后，left下标不是最大值下标了
swap(array,minIndex,left);
if(left ==maxIndex){
maxIndex =minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
冒泡排序
思想：
每次从最小下标开始，与下一个元素进行比较，如果左边比右边大，二者交换，直到待排序序列末尾-1的位置为止，在最坏情况下需要循环上述步骤array.length-1次 ， 这段过程就像冒泡一样，故称为冒泡排序。
public void bubblesort(int[] array){
//冒号排序每次比较出一个最大的值
for (int i = 0; i <array.length-1 ; i++) {
//对冒号排序进行优化，在冒号排序过程中，有可能一轮比较已经达到有序
boolean fig = true;
for (int j = 0; j < array.length-i-1; j++) {
if(array[j]>array[j+1]){
swap(array,j,j+1);
fig =false;
}
}
if(fig ==true){
break;
}
}
}
快速排序
思想： 任取待排序序列中一个数据元素为基准值，按此基准值将此待排序序列分为两部分，小于此基准值划为左待排序序列，大于此基准值的值划为右待排序序列，然后重复此步骤于左右序列，直至所有的数据均变为有序为止。
快速排序有数种实现方法：
我们先介绍挖坑法（必须掌握）：
挖坑法的思想：即在待排序序列中选出了一个基准值以后，将此基准值从所在的数组位置中移到临时变量中，此数组位置便成为一个空位，然后创建两个标记，左标记与右标记，右标记先走，遇到小于基准值的数据则将此值放入当前的空位中，然后左标记再走，直到两者相遇，两者相遇时，此时正指向空位，将临时变量的值赋给此空位，然后将左区间与右区间递归上述操作。
我们取第一个下标的元素为基准值。
//我选取待排序序列的第一个下标的值作为基准值，所以应先移动右标记。
public void quicksort(int []array){
quickwakeng(array,0,array.length-1);
//quickhore(array,0,array.length-1);
}
private void quickwakeng(int []array,int start,int end) {
if (start >= end) {
return;
}
int starttmp = start;
int tmp = array[start];
while (start < end) {
while (array[end] >= tmp && start < end) {
end--;
}
//可以用当前start与end标记当前停止指向的位置，来表示空位置
array[start] = array[end];
//此时end所指向的空间为空，
while (array[start] <= tmp && start < end) {
start++;
}
array[end] = array[start];
}
array[start] = tmp ;
quickwakeng(array,starttmp,start-1); //start的值一定为0吗？不一定
quickwakeng(array,start+1,array.length-1); //end的值不一定为array.length-1,但是递归时，end不会局限array.lenth-1
}
hoare法的思想：
hoare法也是快速排序的一种实现方法。
其实现思想是，用两个标记分别指向待排序区间的两端，移动left至大于基准值的数据下标，移动right至小于基准值的数据下标，当left遇到大于基准值的数据并且right遇到小于基准值的数据，则两者进行交换，直到left==right,即而在左区间与右区间进行相同递归操作。
private void quickhore(int []array,int start,int end){
if(start>=end){
return;
}
//确定基准值
int tmpleft = start;
while (start<end){
//先走右边的指标
while (array[end]>=array[tmpleft]&&start<end){
end--;
}
//此时找到end指向小于基准值的值
while (array[start]<=array[tmpleft]&&start<end){
start++;
}
//此时找到start标记指向的大于基准值的值
swap(array,start,end);
//如果start等于end时，此时交换不会出现错误。
}
//当start等于end时：交换当前值与基准值
swap(array,tmpleft,start);
quickhore(array,tmpleft,start-1);
quickhore(array,start+1,array.length-1);
}
快速排序的优化：
当快速排序遇到有序数据或逆序数据时，其时间复杂度会达到O(N^2), 空间复杂度会达到O(N),如果数据过多，会导致内存崩溃，举例：
所以需要优化算法思想，优化思想：
private void quickwakeng(int []array,int start,int end) {
if (start >= end) {
return;
}
int midIndex = getMiddle(array,start,end);
swap(array,start,midIndex);
//我们需要对下面这段代码逻辑进行封装一下
int pivot = partition(array,start,end);
quickwakeng(array,start,pivot-1); //start的值一定为0吗？不一定
quickwakeng(array,pivot+1,end); //end的值不一定为array.length-1,但是递归时，end不会局限array.lenth-1
}
private int getMiddle(int[] array, int left, int right) {
int mid = (left+right)/2;
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]) {
return right;
}else {
return mid;
}
}else {
if(array[mid] > array[left]) {
return left;
}else if(array[mid] < array[right]) {
return right;
}else {
return mid;
}
}
}
归并排序
归并排序的思想：
归并排序的递归实现：
//归并排序递归实现
private void recursionincorporate(int []array,int left,int right){
//如果划分的数组宽度只有一个元素大小时，则返回
if(left>=right){
return;
}
//获取中间下标
int mid = (left+right)/2;
//划分数组
recursionincorporate(array,left,mid);
recursionincorporate(array,mid+1,right);
//划分数组完成后：开始进行合并，进行直接插入排序,
//这样岂不是多此一举，合并时不应该采用直接插入排序
//insertRangeSort(array,left,right);
merge(array,left,right,mid);
//排序完成后，返回上一个函数
}
private void merge(int []array,int left,int right,int mid){
//将有序的数据先存放到临时的数组中去
int[] tmp = new int[right-left+1];
//对指定区间内两组数据进行排序
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int k = 0;
while (s1<=e1&&s2<=e2){
if(array[s1]<=array[s2]){
tmp[k++] = array[s1++]; //如何设置临时数组的下标？我们需要循环一次，便++的下标，设置即可
}else {
tmp[k++] = array[s2++];
}
}
//当退出循环时，说明有一个数组已经赋值完毕
while (s1<=e1){
//此时说明s2传送完毕
tmp[k++] = array[s1++];
}
while (s2<=e2){
tmp[k++] = array[s2++];
}
//将所有的有序数据存储到临时数组中后
//赋值给array数组
// right是数组的下标范围，还不能表示临时数组中元素的个数。
// for (int i = 0; i <=right; i++) {
for (int i = 0; i <k; i++) {
array[i+left] = tmp[i];
}
}
归并排序的非递归实现：
图解：
//归并排序的非递归实现：
private void no_recursionincorporate(int[] array){
//循环遍历数组，根据不同的gap值来对分数组进行排序
for (int gap = 1; gap <= array.length ; gap*=2) {
//获取每一个分组的左下标与右下标与中间下标
for (int i = 0; i+gap < array.length-1; i+=gap) {
int right = i+gap-1;
int mid = (right+i )/2;
merge(array,i,right,mid);
}
}
}
private void merge(int []array,int left,int right,int mid){
//将有序的数据先存放到临时的数组中去
int[] tmp = new int[right-left+1];
//对指定区间内两组数据进行排序
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int k = 0;
while (s1<=e1&&s2<=e2){
if(array[s1]<=array[s2]){
tmp[k++] = array[s1++]; //如何设置临时数组的下标？我们需要循环一次，便++的下标，设置即可
}else {
tmp[k++] = array[s2++];
}
}
//当退出循环时，说明有一个数组已经赋值完毕
while (s1<=e1){
//此时说明s2传送完毕
tmp[k++] = array[s1++];
}
while (s2<=e2){
tmp[k++] = array[s2++];
}
//将所有的有序数据存储到临时数组中后
//赋值给array数组
// right是数组的下标范围，还不能表示临时数组中元素的个数。
// for (int i = 0; i <=right; i++) {
for (int i = 0; i <k; i++) {
array[i+left] = tmp[i];
}
}
计数排序
一会再写…
