苏州网络推广定制,网站seo外链,产品推广策划案,专业做二手房装修网站0、复杂度及稳定性
时间复杂度空间复杂度 稳定性#xff08;相等元素相对顺序不变#xff09; 冒泡排序 时间复杂度为O(n^2) 最坏/平均#xff1a;O(n^2) 最好#xff1a;O(n)#xff0c;序列有序 O(1)稳定插入排序 时间复杂度为O(n^2) 最坏/平均#xff1a;O(n^2) 最好…0、复杂度及稳定性
时间复杂度空间复杂度 稳定性相等元素相对顺序不变 冒泡排序 时间复杂度为O(n^2) 最坏/平均O(n^2) 最好O(n)序列有序 O(1)稳定插入排序 时间复杂度为O(n^2) 最坏/平均O(n^2) 最好O(n)序列有序 O(1)稳定选择排序O(n^2)O(1)不稳定希尔排序O(nlogn) O( )O(n^2)O(1)不稳定快速排序 O(nlogn) 最坏O(n^2)逆序 O(logn)不稳定归并排序O(nlogn)O(n)稳定堆排序O(nlogn)O(1)不稳定桶排序 最好O(n) 最坏/平均与数据分布有关 O(nk) k是桶的数量 稳定计数排序O(nk) O(k) k是待排序序列中最大值与最小值的差 稳定基数排序 O(d(nk)) d为位数n为数据总数 k为最大数的位数 O(nk) k为最大数的位数 稳定
一、冒泡排序
比较相邻的元素若顺序错误则交换
public void bubbleSort(int[] array) {for (int i 0; i arr.length - 1; i) { for (int j 0; j arr.length - i - 1; j) { if (array[j] array[j1]) { // 交换 array[j] 和 array[j1] int temp array[j]; array[j] array[j1]; array[j1] temp; } } }
}
二、插入排序
将一个待排序的元素按其大小插入到已排序的序列中的适当位置直到全部插入完
public void insertionSort(int[] array) { int n array.length; for (int i 1; i n; i) { int key array[i]; int j i - 1; while (j 0 array[j] key) { array[j 1] array[j]; j j - 1; } array[j 1] key; }
}
三、选择排序
在未排序序列中找到最小元素存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
public void selectionSort(int[] array) { for (int i 0; i array.length - 1; i) { // 找到最小元素的索引 int minIndex i; for (int j i 1; j array.length; j) { if (array[j] array[minIndex]) { minIndex j; } } // 将找到的最小元素交换到已排序序列的末尾 int temp array[minIndex]; array[minIndex] array[i]; array[i] temp; }
}
四、希尔排序
插入排序的一种更高效的改进版
public void shellSort(int[] array) { int n array.length; int gap, i, j, temp; // Start with a big gap, then reduce the gap for (gap n / 2; gap 0; gap / 2) { for (i gap; i n; i 1) { temp array[i]; for (j i; j gap array[j - gap] temp; j - gap) { array[j] array[j - gap]; } array[j] temp; } }
}
五、快速排序
采用分治法。选择一个“基准”元素通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比基准元素小另一部分的所有数据都比基准元素大。以此类推达到有序
public void quickSort(int[] array, int low, int high) { if (low high) { // 找到基准元素的正确位置 int pi partition(array, low, high); // 分别对基准元素两侧的子序列进行递归排序 quickSort(array, low, pi - 1); quickSort(array, pi 1, high); }
} /* 基准元素分割 */
public int partition(int[] array, int low, int high) { // 选择最右侧的元素作为基准元素 int pivot array[high]; int i low - 1; // 指向比基准元素小的元素 for (int j low; j high; j) { // 如果当前元素小于或等于基准元素 if (array[j] pivot) { i; // 交换两个元素 int temp array[i]; array[i] array[j]; array[j] temp; } } // 将基准元素放到正确的位置 int temp array[i 1]; array[i 1] array[high]; array[high] temp; return i 1;
}
六、归并排序
先递归分解数组再将已有序的子序列合并得到完全有序的序列 public void mergeSort(int[] array, int left, int right) { if (left right) { // 找到中间位置 int mid (left right) / 2; // 对左半部分进行归并排序 mergeSort(array, left, mid); // 对右半部分进行归并排序 mergeSort(array, mid 1, right); // 合并左右两部分 merge(array, left, mid, right); }
} public void merge(int[] array, int left, int mid, int right) { // 创建一个临时数组来辅助归并操作 int[] temp new int[right - left 1]; // 左指针和右指针分别指向左半部分和右半部分的起始位置 int i left; int j mid 1; int k 0; // 合并两个有序数组到临时数组 while (i mid j right) { if (array[i] array[j]) { temp[k] array[i]; } else { temp[k] array[j]; } } // 将左半部分剩余的元素复制到临时数组 while (i mid) { temp[k] array[i]; } // 将右半部分剩余的元素复制到临时数组 while (j right) { temp[k] array[j]; } // 将临时数组中的元素复制回原数组 for (i 0; i temp.length; i) { array[left i] temp[i]; }
}
七、堆排序
利用堆进行排序
public class Heap T extends ComparableT{//定义一个数组来存储堆中的元素private T[] items;//记录堆中元素个数private int Num;public Heap(int capacity){//因为T继承了Comparable接口所以这里是new Comparable类型数组this.items (T []) new Comparable[capacity1]; this.Num 0;}//判断堆中索引i处的元素是否小于索引j处的元素private boolean less(int i, int j){return items[i].compareTo(items[j]);}//交换堆中i索引和j索引处的值private void exchange(int i, int j){T temp items[i];items[i] items[j];items[j] temp;}//往堆中插入一个元素public void insert(T t) {//因为数组数量Num初始化为0而这里堆中第一个元素item[0]是不存放任何数值的//所以使用Num跳过了第一个items【0】items[Num] t;rise(Num);}//上浮算法使索引k处的元素能在堆中处于一个正确的位置private void rise(int k){//通过循环不断比较当前结点的值和其父结点的值如果当前结点大于父结点就交换两者位置while(k1){//比较当前结点和其父结点if(less(k/2,k)){exchange(k/2,k);k k/2;}else{break;}}}//删除堆中最大的元素并返回这个最大元素public T delMax(){T max items[1];//交换索引1处元素和最大索引处的元素让完全二叉树最右侧的元素变为临时根结点exchange(1,Num);//删除交换操作后的最大索引处的元素items[Num] null;//元素个数减1Num--;//通过下沉算法重新排列堆sink(1);return max;}//下沉算法使索引k处的元素能在堆中处于一个正确的位置private void sink(int k){//通过循环不断比较当前k结点和其左子结点2*k以及右子结点2*k1处的较大值的元素大小//当前结点小则交换与子节点中最大值的位置while(2*kNum){//获取当前结点的子结点的最大结点int max;if(2*k1Num){ //判断当前结点是否有右子结点if(2*k2*k1){max 2*k1;}else{max 2*k;}}else{max 2*k;}//比较当前结点和较大结点的值if(!less(k,max)){break;}//交换k索引的值和max索引处的值exchange(k,max);//交换k的值k max;}}
}八、桶排序
1、数据分桶桶编号 (数组元素 - 最小值) * (桶个数 - 1) / (最大值 - 最小值)
2、每个桶排序
3、遍历
/*** 桶排序**/
public static void bucketsort(int[] arr, int bucketSize) {// 初始化最大最小值int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;// 找出最小值和最大值for (int num : arr) {max Math.max(max, num);min Math.min(min, num);}// 创建bucketSize个桶ListListInteger bucketList new ArrayList();// 声明五个桶for (int i 0; i bucketSize; i) {bucketList.add(new ArrayList());// 确定桶的格式为ArrayList}// 将数据放入桶中for (int num : arr) {// 确定元素存放的桶号int bucketIndex (num - min) * (bucketSize - 1) / (max - min);// 将元素存入对应的桶中ListInteger list bucketList.get(bucketIndex);list.add(num);}// 遍历每一个桶for (int i 0, arrIndex 0; i bucketList.size(); i) {ListInteger list bucketList.get(i);// 对每一个桶排序list.sort(null);for (int value : list) {arr[arrIndex] value;}}
}九、计数排序
/*** 计数排序**/
public static void countingSort(int[] arr) {if (arr.length 0) {return;}// 原数组拷贝一份int[] copyArray Arrays.copyOf(arr, arr.length);// 初始化最大最小值int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;// 找出最小值和最大值for (int num : copyArray) {max Math.max(max, num);min Math.min(min, num);}// 新开辟一个数组用于统计每个元素的个数(范围是最大数-最小数1)int[] countArray new int[max - min 1];// 增强for循环遍历for (int num : copyArray) {// 加上最小偏差是为了让最小值索引从0开始同时可有节省空间每出现一次数据就加1// 真实值偏差索引值countArray[num - min];}// 获取数组的长度int length countArray.length;// 计数数组变形新元素的值是前面元素累加之和的值for (int i 1; i length; i) {countArray[i] countArray[i] countArray[i - 1];}// 遍历拷贝数组中的元素填充到原数组中去从后往前遍历for (int j copyArray.length - 1; j 0; j--) {// 数据对应计数数组的索引int countIndex copyArray[j] - min;// 数组的索引获取//计数数组的值n就是表示当前数据前有n-1个数据,数组从0开始故当前元素的索引就是n-1int index countArray[countIndex] - 1;// 数组中的值直接赋值给原数组arr[index] copyArray[j];// 计数数组中对应的统计值减1countArray[countIndex]--;}
}十、基数排序
/*** 基数排序**/
public static void radixSort(int[] arr) {// 初始化最大值int max Integer.MIN_VALUE;// 找出最大值for (int num : arr) {max Math.max(max, num);}// 我们这里是数字所以初始化10个空间采用LinkedListLinkedListInteger[] list new LinkedList[10];for (int i 0; i 10; i) {list[i] new LinkedList();// 确定桶的格式为ArrayList}// 个位数123 / 1 % 10 3// 十位数123 / 10 % 10 2// 百位数: 123 / 100 % 10 1for (int divider 1; divider max; divider * 10) {// 分类过程(比如个位、十位、百位等)for (int num : arr) {int no num / divider % 10;list[no].offer(num);}int index 0; // 遍历arr原数组// 收集的过程for (LinkedListInteger linkedList : list) {while (!linkedList.isEmpty()) {arr[index] linkedList.poll();}}}
} 计数排序每个桶只存储单一键值桶排序每个桶存储一定范围的数值基数排序根据键值的每位数字来分配桶
