The sequence table (that is, the array) we have learned can perform many operations on it, such as sorting and searching. Let’s learn sorting and searching today
One: Sort:
One: Bubble sorting (idea: compare two numbers, put the largest or smallest element in the last i loop to control how many times the elements are compared, the inner loop j It is to control the number of comparisons of elements in one trip. For the comparison of two adjacent numbers, a maximum or minimum value can be found in each round and put at the end)
The code is implemented as follows:
void bubbSort(int arr[],int len){
int i,j,temp; //Define outer loop variable i, inner loop variable j, temporary variable temp
for(i=0;i<len-1;i + + ){ // how many times the outer control element is compared
for(j=0;j<len-i-1;j + + ){ //The number of comparisons of inner control elements
if(arr[j]>arr[j + 1]){ //Sort from small to large
temp=arr[j];
arr[j]=a[j+1];
arr[j+1]=temp;
}
}
}
}
int main(){
int arr[10];
int i;
for(i=0;i<10;i ++ ){
printf("Please enter the element %d:",(i + 1));
scanf("%d", &arr[i]);
}
bubbSort(arr,10);
for(i=0;i<10;i ++ ){
printf("%d ",arr[i]);
}
}
Two: simple selection sorting (idea: find the largest or smallest element and put it forward, divide it into a sorted sequence and a sequence to be sorted, and find it from the sequence to be sorted for the first time A maximum or minimum value is placed at the beginning of the sequence, and a variable min is defined to store the subscript of the minimum value. The j loop starts from the next digit of i to find elements smaller/larger than min)
The code is implemented as follows:
void selectSort(int arr[],int len){
int i,j,t,min;
for(i=0;i<len;i ++ ){
min=i; //min marks the position of the unsorted first element
for(j=i + 1;j<len;j + + ){ //Find elements smaller than min
if(arr[min]>arr[j]){
min=j
}
}
if(min!=i){ //If the position of the minimum value is not i, exchange the position of the minimum value and the i-th element
t=arr[min];
arr[min]=arr[i];
arr[i]=t;
}
}
}
int main(){
int arr[10];
int i;
for(i=0;i<10;i ++ ){
printf("Please enter the element %d:",(i + 1));
scanf("%d", &arr[i]);
}
selectSort(arr,10);
for(i=0;i<10;i ++ ){
printf("%d ",arr[i]);
}
}
Three: direct insertion sorting (understand the first number as ordered, and the position of the direct insertion sorting i subscript starts from 1, Then define a temporary variable temp to temporarily store the data at the current subscript position of i in temp. The cycle of j starts from the previous bit of i. For unsorted data, scan from back to front in the sorted sequence to find Corresponding position and insert. Move each subsequent number forward one by one until it finds the position where it can be placed.)
The code is implemented as follows:
//direct insertion sort
int insert (int arr[], int len){
int i,j,temp;
for(i=1;i<len;i + + ){
temp=arr[i];
for(j=i-1;j>=0 & amp; & amp; arr[j]>temp ;j--){
arr[j + 1]=arr[j];
}
arr[j+1]=temp;
}
}
int main(){
int arr[10];
int i;
for(i=0;i<10;i ++ ){
printf("Please enter the element %d:",(i + 1));
scanf("%d", &arr[i]);
}
insert(arr,10);
for(i=0;i<10;i ++ ){
printf("%d ",arr[i]);
}
}
Four: Hill sorting (we learned direct insertion sorting above, and Hill sorting is an improved version of direct insertion sorting, called “shrinking increment”, To write Hill sorting, we need to define the step size. The step size I defined in the following code is accepted by dk. Every time, the step size is used as the benchmark to find the data and sort them from large to small or small to large. , and finally when the step size reaches 1, we can sort all its data, and finally achieve the sorting from large to small or small to large)
The code is implemented as follows:
// Hill sort
int shellSort(int arr[],int len,int dk){
int i,j,temp;
for(i=dk;i<len;i + + ){
if(arr[i]<arr[i-dk]){
temp=arr[i];
j=i-dk;
for(;j>=0 & amp; & amp; arr[j]>temp;j-=dk){
arr[j + 1]=arr[j];
}
arr[j+1]=temp;
}
}
}
int main(){
int arr[6];
int i;
for(i=0;i<6;i ++ ){
printf("Please enter the element %d:",(i + 1));
scanf("%d", &arr[i]);
}
int b[2]={2,1};
int dk;
for(int k=0;k<2;k++){
dk=b[k];
}
shellSort(arr,6,dk);
for(int i=0;i<6;i ++ ){
printf("%d ",arr[i]);
}
}
Five: quick sorting (quick sorting needs to use recursion to achieve, define a benchmark value, and low is the first half, high is the second half, if you want to When it comes to a large sequence, high is greater than the reference value and does not move, and high moves forward. High is to find data that is smaller than the reference value. When it is found, the data at the high position will be given to the low position, and vice versa low is to find data that is larger than the benchmark value. If it is not found, it will go backwards. If it is found, the data at the low position will be given to the high position. In the following code, I use the partition function to partition the data)
The code is implemented as follows:
//quick sort
int fenqu(int arr[],int len,int low,int high){
int pivot=arr[low];
while(low<high){
while(low<high & amp; & amp; arr[high]>pivot){
high--;
}
arr[low]=arr[high];
while(low<high & amp; & amp; arr[low]<=pivot){
low + + ;
}
arr[high]=arr[low];
}
arr[low]=pivot;
return low;
}
int quickSort(int arr[],int len,int low,int high){
if(low<high){
int d=fenqu(arr,len,low,high);
// operate on the left
quickSort(arr,len,low,d-1);
// operate on the right
quickSort(arr,len,d+1,high);
}
}
int print(int arr[],int len){
for(int i=0;i<len;i ++ ){
printf("%d ",arr[i]);
}
}
int main(){
int arr[10];
int i;
for(i=0;i<10;i ++ ){
printf("Please enter the element %d:",(i + 1));
scanf("%d", &arr[i]);
}
int low=0,high=10-1;
quickSort(arr,10,low,high);
print(arr,10);
}
Two: search (our common search includes sequential search, binary search, binary search is divided into recursive and non-recursive, block search)
1: sequential search (sequential search is to traverse the array, and then compare the data to be searched in turn, return the subscript if found, and return -1 if not found)
The code is implemented as follows:
//order search
int findValue(int arr[],int len,int value){
int i;
for(i=0;i<len;i ++ ){
if(value==arr[i]){
return i;
}
}
return -1;
}
int main(){
int arr[10]={2,1,3,5,4,6,8,7,9,10};
int value;
printf("Please enter the data you want to find:");
scanf("%d", &value);
int d=findValue(arr,10,value);
if(d==-1){
printf("Find failed, the element was not found");
}else{
printf("The search is successful, the subscript is: %d", d);
}
}
Two: Half search (also known as binary search, the characteristic of half search is that the data must be in order. Half search is divided into recursive and non-recursive, and half search needs to be used A head (low) and a tail (high) need a middle subscript. When the input data is equal to the middle position data, the subscript will be returned directly. Otherwise, it depends on whether the sequence is from large to small or small to large. If it is small to large, the input When the data is greater than the median value, the head moves and the tail does not move)
The non-recursive code is as follows:
//Binary search (non-recursive)
//arr array, low left value high right value key key to search
int binary(int arr[],int low,int high,int key){
int mid; // intermediate value
while(low<=high){ //The termination condition of the loop is that the minimum subscript is greater than the maximum subscript, that is, there are no elements in the area
mid=(low + high)/2; //Find the middle position
if(key==arr[mid]){
return mid; //return subscript
}else if(key>arr[mid]){
low=mid + 1;
}else{
high=mid-1;
}
}
//keyword not found
return -1;
}
int main(){
int arr[10]={2,8,10,12,15,19,23,26,29,33};
int value;
printf("Please enter the data you want to find:");
scanf("%d", &value);
int low=0,high=10-1;
int d=binary(arr,low,high,value);
if(d==-1){
printf("Find failed, the element was not found");
}else{
printf("The search is successful, the subscript is: %d", d);
}
}
The recursive code is as follows:
//Binary search (recursive)
int binary(int arr[],int low,int high,int key){
int mid; // middle subscript
if(low<=high){ //The termination condition of the loop is that the minimum subscript is greater than the maximum subscript, that is, there are no elements in the area
mid=(low + high)/2;
if(key==arr[mid]){
return mid; //recursive exit
}else if(key>arr[mid]){
return binary(arr,mid + 1,high,key);
}else{
return binary(arr,low,mid-1,key)
}
//keyword not found
return -1;
}
int main(){
int arr[10]={2,8,10,12,15,19,23,26,29,33};
int value;
printf("Please enter the data you want to find:");
scanf("%d", &value);
int low=0,high=10-1;
int d=binary(arr,low,high,value);
if(d==-1){
printf("Find failed, the element was not found");
}else{
printf("The search is successful, the subscript is: %d", d);
}
}
Three: block search (first block the original array (the condition for block is that the data in the original array must have a clear interval, otherwise it cannot be block), from Traverse all critical conditions forward and backward, find the interval where n is located, use sequential search to traverse the target interval, and find the target)
The code is implemented as follows:
//block search
int main(){
int a[12]={12,15,11,13,14,17,9,5,4,0,2,1};
//Create an index table (5 numbers are a group)
int suo[2]={11,0};
//Through the data in the index table, determine which interval
//Enter the data to be searched
int n;
printf("Please enter the data you want to find:");
scanf("%d", &n);
int i,d;
// Find the range where the data is located
for(i=0;i<2;i ++ ){
if(n>=suo[i]){
break;
}
}
if(i==2){
printf("The data is not in the array!");
}
else{ //Data is in the range
// Find the starting subscript of the range
int j=6*i;
int k;
for(k=0;k<6;k++){
if(n==a[j + k]){
printf("The array contains %d, its subscript is: %d", n, j + k);
return 0;
}
}
printf("The array does not include %d!", n);
}
}