今天复习了五个排序，分别是冒泡排序，选择排序，插入排序，哈希排序和快速排序；
然后看了thinking in java的第一章和第二章；
下面就是今天学的所有知识
1.冒泡排序：冒泡排序主要是对邻近的数据进行比较，根据结果判断是否进行交换，一轮一轮挑出其中比较大（小）的数据放到数组末尾；在一轮一轮比较中，需要比较的数据一次减少一个，直到最后下标为0和1的进行比较后，则代表数组已经有序了。
下面是实现代码：
冒泡排序
在这里面，upper用来决定每一轮进行排序的数据个数，由于下标可以为0且内部有sc[i+1]代码的存在，所以里层for循环的取值为：0~sc.length-2;
2.选择排序：这个选择排序和冒泡排序进行比较的次数相等，不过这里是一次性找出一轮数据中最大（小）的数据，放在数组末尾（开头），然后下一轮取其他的数据再一次进行选取最大（小）值；
下面是实现代码：
选择排序
这里实现的是一个从小到大的排序。首先upper和上面一样取值：1~sc.length-1，在表循环中，将sc[0]设置为最大值，然后数据判断从下标1开始，若有sc[n]<sc[0]则把最大值的下标由0换成n，最后判断一下最后的数据是否是下标代表的最大值，不是则把下标代表的最大值和最后面的值做一个交换，这样就完成了一次排序；
这里的子循环中的i可以为1，这代表sc[0]和sc[1]进行比较；
3.插入排序：插入排序是把一个数组分成了三个部分：有序部分，待插入值，无序部分；有序部分的个数由1~sc.length-1；当最后一个数据也进入了有序队列，则排序完成；插入排比价序主要是将待插入值放入有序队列中去，通过比较，将它插入到队列中形成一个有序的新队列；
下面是插入排序的代码：
插入排序
其中count代表待插入值的下标，1~sc.length-1；然后子循环中用num来存储待插入值，让每一个值和他比较，若待插入值小于比较的值，则把比较的值直接后移一位；i=1时代表前面所有数据都大于待插入值，所以就把该值放在0下标处；
4.哈希排序：哈希排序是一个改良版的插入排序，它主要是通过选取一定的间隔，在早期就把离正确位置很远的数据直接一次性转移过去，而不需要插入排序一样一次一次比较复制慢慢地转移过去。在大量数据中，他的速度要比插入排序好很多，而且它在数据逆行的情况下，速度比插入排序快了很多；下面是哈希排序的代码，这个我自己也不是很明白；
希尔排序
这里的num就是选取的固定间隔，num遵循一种算式，让每一个num互成质数，这样的效率是最高的；第一次排序，对下标为：num~sc.length-1的数据进行了间隔为num的数组的排序，注意这里子循环判断条件已经发生改变了；然后按公式慢慢减小num,最后直到为1时，代表数据已经排序完成；
哈希排序和插入排序最大的不同之处在于 sc[i] = sc[i-1] 和 sc[i] = sc[i-num]；
5.快速排序：快速排序主要是应用了一个递归和划分的概念。划分指的是取一个值，将数组中的数据分成两部分，左边的全部小于该数据，右边的全部大于等于该数据；然后又把左边和右边两个数组用这个方法，分到最后，所有数据已经做到了有序状态了；这个排序要分成两个部分，一个是递归的部分，另一个是划分的部分；
划分部分
递归部分
这个函数采用的是直接把数组最右边的数据作为他的中间值（枢纽），然后在划分后，把枢纽放在两个部分中间，此时该数据已经存在了正确排序的位置了，然后对两边两组新数组进行排序……
在划分阶段，我们设置了一个左指针和右指针，分别判断两头的数据和枢纽的关系，若左侧存在大于枢纽的值并且右侧存在小于枢纽的值，则将两个值进行交换，然后继续判断，直到两个指针相等或擦肩而过，则代表该已经划分成功，这时候把最右端数据和右数组的第一个数据进行交换，则完成了划分的功能了。返回的是中间枢纽的下标值；
网友评论