为什么代码1的结果和代码2的结果不一样呢?原理是什么
代码1
long ua { 1000 };
long long* uptr { (long long*)&ua };
std::cout << *uptr;
```c++
代码2
long ua { 1000 };
long long uptr { (long long) ua };
std::cout << uptr;
```
快速排序的思想就是通过不断转换轴点元素最终完成排序
什么是轴点元素?
按升序排序来说,轴点元素就是左边所有元素比该元素小,右边所有元素比该元素大
以下面的图为例子,我们首先需要假设一个轴点元素,然后将所有比它小的放在它左边,比它大的放在它右边,然后通过递归的方式完成最终的排序
过程如下:
1)首先要先定义两个指针,开始时分别指向首尾,分别为left,right
2)假设以第一个元素为轴点元素,我们首先从又右开始往左扫描,用right位置的值与假设索引值进行比较,
①如果比pivot元素值大就不动,并且right指针向左移动一次,重复上述操作
②如果比pivot元素值小就将值赋给left所对应的位置,left向右移动一次,此时需要反向,从左往右开始扫描,重复上述操作
3)重复上述2的操作直到临界点,即left < right,退出操作
4)将假设轴点元素的值赋给最后的索引所在的位置,并返回索引
此时第一轮的选取轴点元素就完成了,且我们可以知道轴点元素左边都是比轴点元素小的,我们可以从left到轴点元素为界限再选取一次轴点元素,以轴点元素到right为界限选取一次轴点元素,依次类推,我们可以很轻松的就将所有元素排好序了,递归时我们需要确定明确的界限保证递归函数能够回溯,不然会造成死循环的情况,我们可以知道此时的界限就是需要left < right,在这个界限内可以一直调用函数直到满足界限,即只剩下一个元素,也就保证了所有元素的排序成功了
代码如下:
public class QuickSort {
public static void main(String[] args) {
int[] arr = {6,3,5,8,1,9,7,2,0};
int i = pivotIndex(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
//对[begin,end) 范围内的元素进行快速排序
public static void quickSort(int[] arr,int begin,int end){
if (end - begin < 2){
return;
}
//对范围内元素进行快速排序确定轴点
int mid = pivotIndex(arr, begin, end);
//对轴点元素左边进行快速排序
quickSort(arr, begin, mid);
//对轴点元素右边进行快速排序
quickSort(arr, mid + 1, end);
}
/**
* 构建范围在[begin,end)范围内元素的轴点元素
*
* @return 返回轴点元素的最终位置
*/
public static int pivotIndex(int[] arr,int begin,int end){
//备份begin元素值
int pivot = arr[begin];
//将end元素指向最后一个元素
end--;
//具体操作逻辑构建轴点元素位置
while (begin < end){
while(begin < end){
//从右往左判断
if (pivot < arr[end]){
end--;
}else {
arr[begin++] = arr[end];
break;
}
}
while(begin < end){
//从左往右判断
if (pivot > arr[begin]){
begin++;
}else {
arr[end--] = arr[begin];
break;
}
}
}
//将备份的轴点元素放入最终的位置
arr[begin] = pivot;
return begin;
}
}
代码1中,uptr是一个指针,指向ua的内存地址,所以输出的是ua的值,也就是1000;而代码2中,uptr是一个long long类型的变量,将ua的值强制转换为long long类型,所以输出的是ua转换后的值,而不是ua本身的值。