排序:就是将一组无序的记录序列按照某种逻辑顺序重新排序,调整为有序的记录序列的过程。简单的说,对于一组记录序列而言,就是根据记录的关键字递增顺序或者递减关系,将记录的次序进行重新排列,使得原来一组次序任意的记录序列转变为按其值有序排列的一组记录序列。
由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序算法分为两大类:
对于具有多个相同值的记录序列来说,如果采用的排序算法使得排序前后拥有相同值记录的相对位置保持不变,则称此排序为稳定的,否则就是不稳定的。相应的排序算法可以分为以下两大类:
根据记录在存储介质上的组织方式划分排序算法的种类,可以分为以下两大类:
常见的排序堂去主要有十种:冒泡排序算法、选择排序算法、插入排序算法、希尔排序算法、归并排序算法、快速排序算法、堆排序算法、计数排序算法、桶排序算法、基数排序算法。
按照算法时间复杂度来划分:
冒泡排序法是通过相邻元素之间的比较与交换,使值较小的元素逐步从后面移到前面,值较大的元素从前面移到后面,就像水底的气泡一样向上冒,故称这种排序方法为冒泡排序法。
每次都是从头开始,最末尾放的都是大的元素
class Solution:
def bubble_sort(self, arr):
length = len(arr)
for i in range(1, length): # 最外面循环n-1次
for j in range(0, length-i): # 每次都是从第一个元素开始遍历比较,但末尾不用比较
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def solution(self, arr):
return self.bubble_sort(arr)
n-1
次的比较,并且不移动元素,算法就可结束排序。此时,算法的时间复杂度为O(n) n-1
趟排序,总共进行\sum^{n}_{i=2}(i-1) = n(n-1)/2 次元素的比较,因此,冒泡排序算法的最差时间复杂度为O(n^2) i
趟排序从序列的后n-i+1(i=1,2,…,n-1)
个元素中选择值最小的元素与该n-i+1
个元素的最前面那个元素交换位置,即与整个序列的第i
个位置上的元素交换位置。如此下去,直到i == n - 1
,排序结束。可以简述为:每一趟排序中,从剩余未排序元素中选择一个最小的元素,与未排好序的元素最前面的那个元素交换位置。
i
,既可以作为排序趟数的计算,同时也作为执行第i
趟排序时,参加排序的后n-i+1
个元素的第1个元素的位置min_i
记录这n-i+1
个元素中值最小元素的位置min_i=i
( 即暂时假设序列的第i
个元素为值最小者,以后经过比较后视实际情况再正式确定最小值元素的位置)n-i+1
个元素中选择一个值最小的元素,并保存下标位置到min_i
中i
趟排序比较结束时,如果若有min_i!= i
,则交换两个位置上的元素。如果有min_i == i
,则不需要交换两个位置上的元素class Solution:
def selectionSort(self, arr):
length = len(arr)
for i in range(length-1):
min_i = i # 记录未排序列表中最小数的索引
for j in range(i+1, length):
if arr[j] < arr[i]:
min_i = j
if min_i != i: # 如果最小数的位置与i不一致,说明需要进行交换
arr[i], arr[min_i] = arr[min_i], arr[i]
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.selectionSort(nums)
对于具有n
个元素的序列采用选择排序方法要经过 n-1
趟用排序。
i
趟排序要找出值最小元素都需要进行n-i
次元素之间的比较。因此,整个排序过程需要进行的元素之间的比较次数都相同,为\sum^{n}_{i=2}(i-1) = n(n-1)/2 次。这i -1
个元素是有序序列,后n-i+1
个元素是无序序列。每一次 排序,将无序序列的首元素,在有序序列中找到相应的位置并插入。可以简述为:每一趟排序中,将剩余未排序元素中第一个元素,插入到排序元素中的合适位置上。这有些类似于打扑克,
2〜n-1
个元素作为无序序列class Solution:
def insertionSort(self, arr):
length = len(arr)
for i in range(1, length):
tmp = arr[i]
j = i
while j<i and arr[j-1] > tmp:
arr[j] = arr[j-1] # 往右边移动
j -= 1
arr[j] = tmp # 放到该位置
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.insertionSort(nums)
n
个元素的序列,插入排序算法一共要进行n-1
趟排序i
值只进行一次元素之间的比较,因而总的比较次数最少,为\sum^{n}_{i=2}1 = n-1 ,并不需要移动元素(记录),这是最好的情况最i-1
次元素之间的比较,总的元素之间的比较次数达到最大值,为\sum^{n}_{i=2}(i-1) = n(n-1)/2 希尔排序是基于插入排序的以下两点性质而提出改进方法的:
gap
,然后将参加排序的序列按此间隔数从第 1个元素开始一次分成若干个子序列,即分别将所有位置相隔为gap
的元素视为一个子序列,在各个子序列中采用某种排序算法进行排序gap=1
img
class Solution:
def shellSort(self, arr):
size = len(arr)
gap = size // 2 # 这里暂定先按照一半进行区分
while gap > 0:
for i in range(gap, size):
tmp = arr[i]
j = i
while j>= gap and arr[j-gap] > tmp: # gap间隔对插入排序
arr[j] = arr[j-gap]
j -= gap
arr[j] = tmp
gap = gap // 2 # 缩小间隔gap
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.shellSort(nums)
gap
之间的依赖关系 ,并给出完整的数学分析n
个元素的序列,若gap_1=n/2 ,则经过gap_1=n/2 趟排序后就有gap_p=1 ,因此希尔排序算法的排序总趟数为log_2n 数量级,中间层do - whil循环为n
数量级。当子序列分得越多时,子序列内的元素就越少,最内层的for循环的次数也就越少;反之,当所分的子序列个数减少时,子序列内的元素也随之增多,但整个序列也逐步接近有序,而循环次数却不会随之增加。因此,希尔排序算法的时间复杂度在O(log_2n) 与O(n^2) 之间
n
个记录看成n
个有序子序列(每个子序列总是有序的),每个子序列的长度均为1n
的有序序列class Solution:
def merge(self, left_arr, right_arr):
# 合并两个有序序列
arr = []
while left_arr and right_arr:
if left_arr[0] <= right_arr[0]:
arr.append(left_arr.pop(0))
else:
arr.append(right_arr.pop(0))
arr += left_arr if left_arr else right_arr
return arr
def mergeSort(self, arr):
size = len(arr)
if size < 2: # 递归结束条件
return arr
mid = size // 2
left_arr, right_arr = arr[0: mid], arr[mid:]
return self.merge(self.mergeSort(left_arr), self.mergeSort(right_arr))
def sortArry(self, nums: List[int]) -> List[int]:
return self.mergeSort(nums)
merge(left_arry, right_arry)
的时间复杂度是O(n) ,因此,归并排序算法总的时间复杂度为(n*log_2n) merge(left_arr, right_arry)
算法能够使前一个序列中那个相同元素先被赋值,从而确保这两个元素的相对次序不发生改变,所以归并排序算法是稳定性排序算法img
class Solution:
def randomPartition(self, arr: List[int], low: int, high: int):
i = random.randint(low, high)
arr[i], arr[high] = arr[high], arr[i]
rerurn self.partition(arr, low, high)
def partition(self, arr: List[int], low: int, high: int):
i = low - 1
pivot = arr[high] # 取最右边值作为基准,但是随机更换后最高元素的值,带来的随机性
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1] # 基准点下标是index+1,
return i+1
def quickSort(self, arr, low, high):
if low < high:
pivot = self.randomPartition(arr, low, high)
self.quickSort(arr, low, pivot-1)
self.quickSort(arr, pivot+1, high)
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.quickSort(nums, 0, len(nums)-1)
n-1
次比较以后,第1个元素仍然确定在原来的位置上,并得到 1个长度为n-1
的子序列;第2趟排序进过n-2
次比较以后,将第2个元素确定在它原来的位置上,又得到1个长度为n-2
的子序列;依次类推,最终总的比较次数为因此,时间复杂度为O(n^2)
n
的序列进行快速排序所需要的时间为O(nlog_2n) 堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
n
个元素的最大值处于序列的第1个位置n-1
个元素组成的子序列调整成一个新的大顶堆,这样又得到第2个最大值元素,把子序列的第1个元素(最大值元素)与第n-1
个元素交换位置n-2
个元素调整成一个新的大顶堆,……,如此下去,直到整个序列变换成一个有序序列把移走了最大值元素以后的剩余元素组成的序列再构造为一个新的堆积。具体步骤如下:
i
的节点与其左子树节点(序号为2 * i)
、右子树节点(序号为2*(+1)
中值最大的节点交换位置具体步骤如下:
d
, 则从d-1
层最右侧分支节点(序号为n/2 )开始,初始时令i=n/2 ,调用堆调整算法img
class Solution:
# 调整为大顶堆
def heapify(self, arr: List[int], index: int, end: int):
left = index * 2 + 1
right = left + 1
while left <= end:
# 当前节点为非叶子节点
max_index = index
if arr[left] > arr[max_index]:
max_index = left
if right <= end and arr[rignt] > arr[max_index]:
max_index = right
if max_index == index:
# 如果不用交换,则说明已经交换结束
break
arr[index], arr[max_index] == arr[max_index], arr[index]
# 继续调整子树
index = max_index
left = index * 2 + 1
right = left + 1
def buildMaxHeap(self, arr: List[int]):
# 初始化大顶堆
size = len(arr) # (size-2)//2 是最后一个非叶节点,叶节点不用调整
for i in range((size-2), i, size-1):
self.heapify(arr, i, size-1)
return arr
# 生序堆排序,思路如下:
# 1.先建立大顶堆
# 2.让大顶堆最大元素与最后一个交换,然后调整第一个元素和倒数第二个元素,这一步获取最大值
# 3.再交换堆顶元素与倒数第二个元素,然后调整第一个元素和倒数第三个元素,这一步获取第二大值
# 4.以此类推,直到最后一个元素交换之后结束
def maxHeapSort(self, arr: List[int]):
self.buildMaxHeap(arr)
size = len(arr)
for i in range(size):
arr[0], arr[size-i-1] = arr[size-i-1], arr[0] # 第一个元素与后面的元素进行交换
self.heapify(arr, 0, size-i-2) # 重新调整
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.maxHeapSort(nums)
n
个元素构成的序列所对应的完全二叉树深度为d=log_2n+1 ,算法由两个部分组成:adjust
算法,每一次adjust
算法,对于第i
层一个节点到第d
层上建立的子堆积,所有节点可能移动的最大距离为该子堆积根节点移动到最后一层(第d层)的距制即d-i
i
层上节点最多有2^{i-1} 个,所以每一次adjust
算法最大移动距离为2^{i-1}*(d-i) 。因此,堆积排序算法的第1个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和,即:,这一部分时间花费为O(n)
adjust
算法一次,节点移动的最大距离为这棵完全二叉树的深度d=log_2n+1 ,一共调用了 n-1 次adjust
算法,所以,第2个循环的时间花费为计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
counts
,其中第i
个元素counts[i]
是待排序数组arr
中值等于i
的元素个数。counts
来将arr
中的元素排到正确的位置.counts
数组大小为最下值-最小值+ 1
.i
的元素出现的次数,存入数组的第i
项counts
中的第一行素开始,每一项和前一项累加)i
放在新数组的第counts[i]
项,每放一个元素就要将counts[i]-1
img
class Solution:
def countingSort(self, arr):
arr_min, arr_max = min(arr), max(arr)
size = arr_max - arr_min
counts = [0 for _ in range(size)]
for num in arr:
counts[num-arr_min] += 1
for j in range(1, size):
counts[j] += counts[j-1]
res = [0 for _ in range(len(arr))]
for i in range(len(arr)-1, -1, -1):
res[counts[arr[i]-arr_min]-1] = arr[i]
counts[arr[i]-arr_min] -= 1
return res
def sortArray(self, nums: List[int]) -> List[int]:
return self.countingSort(nums)
n
个0~k
之间的整数时,计数排序的时间复杂度为O(n+k) counts
的长度取决于排排序数组中数据的范围(等于排序数组的最大值减去最小值再加1)。所以计数排序对于数据范围很大的数组,需要大量的时间和内存。桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,需要做到以下两点:
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
n
个相同大小的子区间,每个区间称为一个桶在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
class Solution:
def insertionSort(self, arr):
for i in range(1, len(arr)):
tmp = arr[i]
j = i
while j>0 and arr[j-1] > tmp:
arr[j] = arr[j-1]
j -= 1
arr[j] = tmp
return arr
def bucketSort(self, arr, bucket_size=5):
arr_min, arr_max = min(arr), max(arr)
bucket_count = (arr_max-arr_min)//bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
buckets[(num-min_arr)//bucket_size].append(num)
res = []
for bucket in buckets:
self.insertionSort(bucket)
res.extend(bucket)
return res
def sortArray(self, nums: List[int]) -> List[int]:
return self.bucketSort(nums)
n
,桶的个数是m
时,每个桶里的数据就是k=n/m 个。每个桶内排序的时间复杂度为O(klog_2k) 。m
个就是m*O(klog_2k)=m*O(n/m*log_2(n/m)) = O(n*log_2(n/m)) ,当桶的个数m
接近于数据个数n
时,log_2(n/m) 就是一个较小的常数,所以桶排序时间复杂度接近于O(n) 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
将整数按位切割成不同的数字,然后按每个位数分别比较进行排序。
基数排序算法可以采用最低位优先先法或者最高位优先法。最常用的是最低位优先法。
下面以最低位优先法为例,讲解一下算法步骤
img
class Solution:
def radixSort(self, arr):
size = len(str(max(arr)))
for i in range(size):
buckets = [[] for _ in range(10)]
for num in arr:
buckets[num//(10**i)%10].append(num)
arr.clear()
for bucket in buckets:
for num in bucket:
arr.append(num)
return arr
def sortArray(self, nums: List[int]) -> List[int]:
return self.radixSort(nums)
n
是待排序元素的个数,k
是数字位数。k的大小取决于 数字位的选择(十进制位,二进制位)和待排序元素所属数据类型全集的大小。排序算法是使用比较多的算法,在推荐算法或者搜索算法中都是需要用到的。
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示:
nums1.length == m + n
解题思路
可以看到这个是直接在nums1上进行修改,由于nums1有数值的元素的长度为m,而nums2有数值的元素的长度为n,那么可以从后往前进行遍历:
python实现
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
index1 = m - 1
index2 = n - 1
index = m + n - 1
while index1 >= 0 or index2 >=0:
if nums1[index1] < nums2[index2]:
nums1[index] = nums2[index2]
index2 -= 1
else:
nums1[index] = nums1[index1]
index1 -= 1
index -= 1
# nums2 still have elements
nums1[:index2+1] = nums2[:index2+1]
return nums1
c++实现
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index1 = m - 1;
int index2 = n - 1;
int index = m + n - 1;
while(index1 >= 0 && index2 >= 0)
{
if (nums1[index1] < nums2[index2])
{
nums1[index] = nums2[index2];
index2--;
}
else
{
nums1[index] = nums1[index1];
index1--;
}
index--;
}
if(index1==-1 && index2 != -1) // 如果nums2还有元素没有被遍历,继续遍历和赋值
{
while(index2 != -1)
{
nums1[index] = nums2[index2];
index--;
index2--;
}
}
/* 这部分好像不需要
if(index1 != -1 && index2 == -1)
{
while(index1 != -1)
{
nums1[index] = nums1[index1];
index--;
index1--;
}
}
*/
}
};
给你一个整数数组 nums
,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]
提示:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
解题思路:
实现一个从小到大的排序算法,注意时间复杂度。这里使用归并排序,时间复杂度为O(nlogn)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
return self.merge_sort(nums)
def merge_sort(self, nums):
size = len(nums)
if size < 2:
return nums
mid = size // 2
left_nums, right_nums = nums[0:mid], nums[mid:]
return self.merge(self.merge_sort(left_nums), self.merge_sort(right_nums)) # 递归到一个元素,再合并
def merge(self, left_nums, right_nums):
nums = []
while left_nums and right_nums:
if left_nums[0] <= right_nums[0]:
nums.append(left_nums.pop(0))
else:
nums.append(right_nums.pop(0))
nums += left_nums if left_nums else right_nums
return nums
class Solution {
public:
void merge(vector<int> &nums, int front, int mid, int end)
{
vector<int> left_nums(nums.begin()+front, nums.begin()+mid+1);
vector<int> right_nums(nums.begin()+mid+1, nums.begin()+end+1);
int idx_left = 0;
int idx_right = 0;
//left_nums.insert(left_nums.end(), numeric_limits<int>::max());
//right_nums.insert(right_nums.end(), numeric_limits<int>::max());
for(int i=front; i<= end; i++)
{
if(left_nums[idx_left] < right_nums[idx_right])
{
nums[i] = left_nums[idx_left];
idx_left++;
}
else
{
nums[i] = right_nums[idx_right];
idx_right++;
}
}
}
void merge_sort(vector<int> &nums, int front, int end)
{
if(front >= end)
{
return;
}
int mid = (front+end) / 2;
merge_sort(nums, front, mid);
merge_sort(nums, mid+1, end);
merge(nums, front, mid, end);
}
vector<int> sortArray(vector<int>& nums) {
merge_sort(nums, 0, nums.size());
return nums;
}
};
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序进阶:
O(n)
的算法解决本问题解题思路:
这里实现双指针思路
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
i, j, pos = 0, n-1, n-1
while i <= j:
if nums[i] * nums[i] > nums[j] * nums[j]:
ans[pos] = nums[i] * nums[i]
i += 1
else:
ans[pos] = nums[j] * nums[j]
j -= 1
pos -= 1
return ans
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
int i = 0;
int j = n-1;
int pos = n-1;
vector<int> res(n);
while(i <= j)
{
if(nums[i] * nums[i] > nums[j] * nums[j])
{
res[pos] = nums[i] * nums[i];
++i;
}
else
{
res[pos] = nums[j] * nums[j];
--j;
}
pos--;
}
return res;
}
};
给你两个数组,arr1
和 arr2
,arr2
中的元素各不相同,arr2
中的每个元素都出现在 arr1
中。
对 arr1
中的元素进行排序,使 arr1
中项的相对顺序和 arr2
中的相对顺序相同。未在 arr2
中出现过的元素需要按照升序放在 arr1
的末尾。
示例 1:
输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出:[2,2,2,1,4,3,3,9,6,7,19]
示例 2:
输入:arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出:[22,28,8,6,17,44]
提示:
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2
中的元素 arr2[i]
各不相同arr2
中的每个元素 arr2[i]
都出现在 arr1
中解题思路:
计数排序:注意到本题中元素的范围为0~1000 ,这个范围不是很大,可以考虑不基于比较的排序,例如「计数排序」。具体地,使用一个长度为 (下标从0到1000 )的数组frequency
,记录每一个元素在数组arr1
中出现的次数。随后遍历数组arr2
,当遍历到元素x
时,我们将frequency[x]
个x
加入答案中,并将frequency[x]
清零。当遍历结束后,所有在arr2
中出现过的元素就已经有序了。
此时还剩下没有在arr2
中出现过的元素,因此我们还需要对整个数组frequency
进行一次遍历。当遍历到元素 x
时,如果x
不为 ,我们就将frequency[x]
个x
加入答案中。
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
element_nums = [0] * 1001
for num in arr1:
element_nums[num] += 1
res = []
for num in arr2:
while element_nums[num]:
res.append(num)
element_nums[num] -= 1
for index in range(1001):
while element_nums[index]:
res.append(index)
element_nums[index] -= 1
return res
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> cnt(1001); // 统计频次
int n1 = arr1.size();
int n2 = arr2.size();
// 统计arr1中每个数字出现的次数
for(int a1: arr1)
{
cnt[a1]++;
}
// 将arr2中的每个数字重复放入arr1中
int i = 0;
for(int a2: arr2)
{
while(cnt[a2] > 0)
{
arr1[i] = a2;
i++;
cnt[a2]--;
}
}
// 剩下的依次放入即可
for(int j=0; j<cnt.size(); j++)
{
while(cnt[j] > 0)
{
arr1[i] = j;
i++;
cnt[j]--;
}
}
return arr1;
}
};
给定单个链表的头 head
,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。
插入排序 算法的步骤:
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。
对链表进行插入排序。
img
示例 1:
img
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2:
在这里插入图片描述
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
提示:
[1, 5000]
范围内-5000 <= Node.val <= 5000
解题思路:
插入排序的基本思想是,维护一个有序序列,初始时有序序列只有一个元素,每次将一个新的元素插入到有序序列中,将有序序列的长度增加 ,直到全部元素都加入到有序序列中。
如果是数组的插入排序,则数组的前面部分是有序序列,每次找到有序序列后面的第一个元素(待插入元素)的插入位置,将有序序列中的插入位置后面的元素都往后移动一位,然后将待插入元素置于插入位置。
对于链表而言,插入元素时只要更新相邻节点的指针即可,不需要像数组一样将插入位置后面的元素往后移动,因此插入操作的时间复杂度是O(1) ,但是找到插入位置需要遍历链表中的节点,时间复杂度是O(n) ,因此链表插入排序的总时间复杂度仍然是O(n) ,其中n
是链表的长度。
对于单向链表而言,只有指向后一个节点的指针,因此需要从链表的头节点开始往后遍历链表中的节点,寻找插入位置。
对链表进行插入排序的具体过程如下。
首先判断给定的链表是否为空,若为空,则不需要进行排序,直接返回。
创建哑节点 dummyHead
,令 dummyHead.next = head
。引入哑节点是为了便于在 head
节点之前插入节点。
维护 lastSorted
为链表的已排序部分的最后一个节点,初始时 lastSorted = head
。
维护 curr
为待插入的元素,初始时 curr = head.next
。
比较 lastSorted
和 curr
的节点值。
lastSorted.val <= curr.val
,说明 curr
应该位于 lastSorted
之后,将 lastSorted
后移一位,curr
变成新的 lastSorted
。令 curr = lastSorted.next
,此时 curr
为下一个待插入的元素。
重复第 5 步和第 6 步,直到 curr
变成空,排序结束。
返回 dummyHead.next
,为排序后的链表的头节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head:
return head;
dummyHead = ListNode(0)
dummyHead.next = head
lastSorted = head
curr = head.next
while curr:
if lastSorted.val <= curr.val:
lastSorted = lastSorted.next
else:
prev = dummyHead
while prev.next.val <= curr.val:
prev = prev.next
lastSorted.next = curr.next
curr.next = prev.next
prev.next = curr
curr = lastSorted.next
return dummyHead.next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head == nullptr)
{
return head;
}
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* lastSorted = head;
ListNode* curr = head->next;
while(curr != nullptr)
{
if(lastSorted->val <= curr->val)
{
lastSorted = lastSorted->next;
}
else
{
ListNode* prev = dummyHead;
while(prev->next->val <= curr->val)
{
prev = prev->next;
}
lastSorted->next = curr->next;
curr->next = prev->next;
prev->next = curr;
}
curr = lastSorted->next;
}
return dummyHead->next;
}
};