学网站开发培训,大连市平台网站,网站推广什么意思,信息技术网站建设市场分析目录
一、直接插入排序
二、希尔排序
三、直接选择排序
四、堆排序
五、冒泡排序
六、快速排序
七、归并排序 一、直接插入排序
思想#xff1a; 定义i下标之前的元素全部已经有序#xff0c;遍历一遍要排序的数组#xff0c;把i下标前的元素全部进行排序#xff0…目录
一、直接插入排序
二、希尔排序
三、直接选择排序
四、堆排序
五、冒泡排序
六、快速排序
七、归并排序 一、直接插入排序
思想 定义i下标之前的元素全部已经有序遍历一遍要排序的数组把i下标前的元素全部进行排序当遍历玩这个数组后就已经排好序了。
代码如下
public static void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];int j i - 1;for(; j 0;; j--) {if(array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}
代码解析 要使i下标之前的元素都有序定义一个j下标为i - 1再用tmp记录i下标的位置只要j下标元素比tmp大j下标的元素就要放到j1下标最后j走完后再把最小的tmp放在j1位置。
时间复杂度、空间复杂度、稳定性 时间O(n^2) 空间O(1) 稳定性稳定 二、希尔排序
思想 希尔排序也称缩小增量排序就是分次去进行排序越排到后面就会越有序每次间隔是gap然后逐渐缩小到最后间隔为0也就是用我们的直接插入排序数组越有序速度也会越快。那么就很简单了我们只需改一下直接插入排序每次排序的间隔把他们分成不同组进行排序直到最后间隔为0就只剩一组然后也是用直接插入排序做最后一次排序排完就是有序的了。
图式例 代码如下
public static void shellSort(int[] array) {int gap array.length / 2;while (gap 1) {gap / 2;shell(array, gap);}}public static void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for(; j 0; j - gap) {if(array[j] tmp) {array[j gap] array[j];} else {break;}}array[j gap] tmp;}}
时间复杂度、空间复杂度、稳定性 时间n^1.3(严蔚敏) 因为gap取值方式不同计算出来的时间复杂度也会不同 空间O(1) 稳定性不稳定 三、直接选择排序
思想 直接选择排序也是和直接插入排序差不多定义i下标前的元素全部都有序不过排序的方式不同它是拿i下标前的元素和i下标后的元素进行比较找到下标最小的元素把最小元素放进i下标中同时这个i下标元素放到被这个最小下标位置。
代码实现
public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;//记录最小值的下标for (int j i1; j array.length; j) {if(array[j] array[minIndex]) {minIndex j;}}//走完这里找到最小元素的下标minIndex//交换int tmp array[i];array[i] array[minIndex];array[minIndex] tmp;}}
时间复杂度、空间复杂度、稳定性 时间O(n^2) 空间O(1) 稳定性不稳定 四、堆排序
思想 堆其实就是完全二叉树下标是从上到下从左到右依次递增要把堆排序成升序就要把他先变成大根堆每次出大根堆的顶点把顶点放在最后一个节点然后再向下调整一次第二次把大根堆的顶点放到倒数第二个位置依次往后推。
代码实现
//堆排序public static void heapSort(int[] array) {//先转换成大根堆createHeap(array);//开始换然后向下转换for (int i array.length - 1; i 0 ; i--) {//i下标的节点和堆顶交换int tmp array[0];array[0] array[i];array[i] tmp;//向下调整siftDown(array,0, i);}}
//创建大根堆public static void createHeap(int[] array) {//从最后一个父节点开始向下调整下标依次往前减//parent (child - 1) / 2; 左child parent * 2 1 右child parent * 2 2for (int i (array.length - 1 - 1) / 2; i 0 ; i--) {siftDown(array, i, array.length);}}//向下调整public static void siftDown(int[] array, int parent, int length) {//定义一个child为该父节点的左孩子int child parent * 2 1;while (child length) {//比较改父节点的左右孩子把值最大的孩子作为交换节点if(array[child] array[child 1]) {child 1;}//比较父节点和孩子节点大小if(array[parent] array[child]) {//交换int tmp array[parent];array[parent] array[child];array[child] tmp;parent child;child child * 2 1;} else {break;}}}
时间复杂度、空间复杂度、稳定性 时间复杂度O(NlogN) 空间复杂度O(1) 稳定性不稳定
五、冒泡排序
思想 冒泡排序的思想很简单就是第一次把最大的值放到数组最后一个下标中再把第二大的元素放到数组倒数第二个下标中依次类推
代码实现 //冒泡排序public static void bubbleSort(int[] array) {for (int i 0; i array.length; i) {boolean flag false;//标记for (int j 0; j array.length - 1 - i; j) {if(array[j] array[j 1]) {//交换int tmp array[j];array[j] array[j 1];array[j 1] tmp;flag true;}}if(!flag) {break;}}}
时间复杂度、空间复杂度、稳定性 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 六、快速排序
思想 使用递归思想也可以采用非递归思想把一组数据划分成两部分左边都小于该下标元素右边都大于该下标元素再在左边去找元素划分右边元素去划分依次往后推直到左右两边都没有元素可以划分了就是只剩一个元素了这时候往回倒就有序了
代码实现
public static void quickSort(int[] array) {int left 0;int right array.length - 1;quick(array, left, right);}public static void quick(int[] array, int start, int end) {//递归结束条件if(start end) {return;}int pivot partition(array, start, end);quick(array, start, pivot - 1);quick(array, pivot 1, end);}public static int partition(int[] array, int left, int right) {//找到一个下标元素左边都比这个下标元素小右边都比这个下标元素大并且还要返回这个下标//记录下标为0的值放在tmp中int tmp array[0];while (left right) {//先走右边if(left right array[right] tmp) {right--;}if(left right array[left] tmp) {left;}//左下标的值大于tmp右下标的值小于tmp这两个下标值交换int newTmp array[left];array[left] array[right];array[right] newTmp;}//走到这left和right相遇了,left下标的值和tmp交换,并且返回这个位置的下标int newTmp tmp;tmp array[left];array[left] newTmp;return left;}时间复杂度、空间复杂度、稳定性 时间复杂度O(NlogN) 空间复杂度O(logN~N) 稳定性不稳定 七、归并排序
思想 将一组数组分割成左右两部分和快速排序找出的中件位置不同归并的中间位置是最左和最右下标相加再除2leftright/ 2,运用的也是递归思想也可以采用非递归思想采用分治法一直找到最左边进行排序然后再找最右边进行排序再往归回整体排序合并合并的时候是放在一个临时数组中再把这个临时数组拷贝到原数组下标要对应
代码实现
public static void mergeSort(int[] array) {int start 0;int end array.length - 1;mergeSortFunc(array, start, end);}//套壳public static void mergeSortFunc(int[] array, int start, int end) {//递归结束标志if(start end) {return;}//求出中间节点位置int mid (start end) / 2;//左边mergeSortFunc(array, start, mid);//右边mergeSortFunc(array, mid 1, end);//合并merge(array, start, mid, end);}//合并public static void merge(int[] array, int left, int mid, int right) {//定义mid两边的左右下标int s1 left;int e1 mid;int s2 mid 1;int e2 right;//定义一个新的数组存放array排序完后的数组int[] tmpArray new int[right - left - 1];int k 0;while (s1 e1 s2 e2) {//比较左右两边s1和s2的值if(array[s1] array[s2]) {tmpArray[k] array[s1];} else {tmpArray[k] array[s2];}if(s1 e1) {tmpArray[k] array[s1];}if(s2 e2) {tmpArray[k] array[s2];}}//拷贝到原数组for (int i 0; i tmpArray.length; i) {array[left i] tmpArray[i];}} 时间复杂度、空间复杂度、稳定性 时间复杂度O(NlogN) 空间复杂度O(N) 稳定性不稳定 都看到这了给个免费的赞呗谢谢谢谢
